Since I played in a Kingmaker campaign I have, for a long time been wanting to run one of my own. I have seen the potential problems in this campaign. Recent releases like Ultimate Campaign, Mythic Adventures and the Dragon's Demand have given me an idea.
First, it would start with the Dragon's Demand. I would run the module in it's entirety with the group ending at about levels 7 or 8, possibly 9. I would move the city of Belhaim to Brevoy somewhere, maybe somewhere south but not too far. I would also enable players to make characters using the Kingmaker Player's Guide.
Second, and this is where it gets crazy. I would use character trees. This idea was introduced in Dark Sun as a means of getting around the lethality of the campaign. I want to do this to give the players multiple points of view in the campaign. The tree works like this: you make 3 characters in addition to the main, every time you level, one other character gains a level. The designated "Main" cannot gain levels this way. All of the additional characters are related to the main somehow (relatives, servants, followers, proteges etc). It should be easily possible to fill every post in government with backups with a 5 player group. The group that finishes the Dragon's Demand will form the core of this group. Who better to lead an expedition than a group of famous dragon slayers?
Third, I would split the events of the campaign so that different characters would participate in different parts of the campaign. The high level characters are the rulers doing the main events and the lower levels are the followers doing all the exploring and errand running.
Fourth, and lastly I would try to incorporate the enhanced encounters as well as Redcelt's political background information.
i'm wondering though, am I biting off more than I can chew.
If you're doing multiple characters, which I think is a fun idea, have you checked out Kobold Press's Court of the Shadowfey? I'm reading through it now, and though it is written for the Midgard campaign setting, it's pretty easy to transfer over to Golarion (it runs from levels 7-10). I mention it because I recently ran what was supposed to be a one shot adventure using my PCs' kingdom as the backdrop. They rolled up new characters to tackle Richard Pett's Sorrow adventure and had a really good time. We called them the kingdom's "B team" because, basically, they were taking care of the smaller problems while their regular 12th level PCs were cutting through barbarian armies. If you find you need extra material for the different characters, I recommend that module as you can tie it in pretty nicely with the overarching fey metaplot.
I've had some ideas for how I would run the first part.
-If the PC's decide to send the low level party first the fight at Oleg's still happens. Otherwise, if the PC's move their high level group in force then the fight won't happen
-The Thorn River camp will be more of a small wilderness fort.
-The Stag Lord's operation will be a lot more developed. It will be in a true full scale castle, only in a ruined state. The Stag Lord's bandit kingdom will be in its infancy, and he'll be around level 10.
-The low level PC's will have to map the region and do the low level quests. It's the mid level's that I'll need to find stuff for.
Some other ideas-
-Candlemere. In ancient times it was a valley with a great temple to the old one within. The remains of the temple are deep underneath the island, near the bottom of the lake.
-The Old Beldame- I'm making her a 9th or 10th level witch. She'll be a local legend in those parts.
I've done similar, though it's been handing the reins of various NPCs (Akiros, Mikmek and Chief Sootscale, etc.) over to the party for certain side events.
As my characters progressed, I have them a free leadership feat to represent the entourage they attracted as they became more famous. The only proviso is that the characters they get can only have NPC class levels. That seems to work quite nicely, and I think I will use it again when we move to a new campaign. It can give an A, B and C team if you want them :)