You're right, combat only challenges get pretty boring. So in a long term campaign, it's good to have a bunch of other kinds of things that PCs can spend their time on.
These tend to break down into three different kinds of things.
- Action scenes other than combat
- Non-action skill-driven challenges
- Strategy and Diplomacy
Action Scenes Other Than Combat
I'm running a pirate game and we've had entire sessions that were "man vs nature" scenes where they were trying to keep their ship intact and on course during a storm, for example. Chases, competitions, jousts, sports... Instead of killing the boggard tribe, how about participating in their weird frog sports to win them over? The first RPG I ever owned was Star Frontiers, and in the initial set of modules the PCs crash-land on a planet (Volturnus) and can win over a weird tentacly indigenous alien race, the Ul-Mor, by participating in their version of Buzkashi. Some of these will have similar-to-combat elements, just are more subtle than pure carnage.
Somewhat related are challenges that are still combat, but have a goal other than "kill the other side" - like trying to repair the dam before it floods the village, but there's some agitated bee swarms attacking them. It's a combat, but since the goal isn't the combat per se but to accomplish something (and all the usual options are here - defend a place, take something somewhere, defend a person, or the reverse) then it feels a lot different and can be accomplished in non-straightforward ways by the PCs. Like if a scrag washes up on deck during the storm at sea above; it's not a "CR appropriate encounter" and the goal isn't to fight it, it's more of a combat complication to a non-combat scene (and they'd be happy enough to just push it overboard rather than fight it to the death). Also, just keep in mind that Pathfinder isn't a computer game where all these kinds of challenges have to be separate - you can mix/match/meld them at will (e.g. a duel with a noble where your main goal, besides not dying, is to use the opportunity to lay some charm down on the princess who is attending - a skill challenge amidst a combat).
Non-Action Skill Challenges
Exploration is the most typical example, and there's loads of opportunity for that in Kingmaker. Dungeon exploration is more about obstacles and traps and tricks and puzzles, but outdoor exploration has its own charms as well. Use the weather, make it realistic - getting lost, avoiding encounters, learning about the land. Travel isn't simple without monsters! How do you get your mounts across that crevice? See also What can I do to give the players the same feel their characters would have about wilderness travel? for more on making travel interesting. I like rewarding skill use, so Survival etc. can be used to detect/avoid random encounters, for example. You can make this as crunchy or non-crunchy as you want - there's loads of discussion on this site and others of "old school vs new school" approach to exploration and whether you do it narratively and make them verbally fondle the puzzlebox or whether you just let them roll Disable Device and be done with it. One of the benefits of the former approach is that it gives it more 'screen time' and cuts down on combat's share of your hours.
Strategy and Diplomacy
General planning and creating things is a great challenge for players. In Kingmaker, in fact, the entire kingdom-building part of the system is designed as a huge non-combat type challenge. Can you make a kingdom that makes money? Can it weather the travails of life in the River Kingdoms? Expand on this; if you just use the bare bones provided in the AP then it can be a bit of a flat minigame, but if you have the characters engage in-character with the rounds of building and economics and all, then it is actually the most meaningful challenge of the AP.
Similarly, a lot of Kingmaker can and should be about making friends, enemies, trade partners, etc. Though poor GMs can certainly "turn this into one or two rolls," as @BESW warns, I strongly disagree that this is a necessary path in d20/Pathfinder.
For example, my PCs' pirate crew is always looking for new pirates. Sometimes they impress prisoners, but they also have open calls when they hit a pirate city. They'll spend hours interviewing pirates, checking up on their history, giving them a tryout (sometimes escalating to combat :-)... Sure, I could just have them "roll Diplomacy to see how many recruits you get, they are all indistinguishable level 2 warriors, done" but they really get into the details, so it turns into an hour-long scene instead.
In Kingmaker and other APs you'll find a lot of support for this; they often have whole chapters about choosing who to try to get on your side (often there's some specific quest involved with it, of course...).
But This Is Up To You (and Them)
The AP itself won't have lots of this. Now, it does have hexcrawling and kingdom building rules, but it's easy to treat them as a minigame. They fill page count with big stat blocks and NPC backgrounds. It's up to you to flesh out the actual campaign with the kinds of things your group enjoys.