I'd put it in the hands of a patron known and trusted by the players. Watch them try to figure out what's happening and how to fix it. In the course of figuring things out, they'd end up in some very sticky situations, such as when their patron decides that sacrificing them to a rival is the "easiest" way out of a longer conflict or when notifying them about some danger becomes too much work.
As with Wrathbringer, I somewhat resent the mind control aspect. Corruption is so much sweeter if the mortal got to make all the wrong choices himself.
Usually, it will be sufficient to give a mortal that political acumen, let him know of the plans of the enemies, perhaps serve as a non-sentient depository of knowledge - that coupled with added charisma is usually enough to fuel pride. Once he has a few enemies, the paranoia also comes on its own.
A blade that increases your charisma and political savvy would be very useful indeed, though I imagine that the owner would try to hide the source of his newfound fortune from other potential hosts if he knew. The victim would probably begin to suspect that there was something special about the day he got the blade, and might begin to consider it a lucky talisman of sorts. Those suspicions would only be confirmed when Kingmaker passes on to a new host.
For those reasons, I don't believe that Kingmaker would be very successful in his quest to find more and more powerful hosts. The previous ones would be desperate to get the blade back, and would use what influence they had left to that end. Of course, Kingmaker could hide his appearance at that point so that he won't be recognized, but I'm not sure if that helps.
One question: when you say that Kingmaker changes appearance, do you mean that it physically alters itself into, say, an axe? Or does it use illusion? I ask because you say it tries to make itself appealing to new hosts even while in the possession of another person. Wouldn't the current host notice that his jeweled dagger was suddenly a war axe?
Overall though, an intriguing blade. I'd love to put this into the hands of a PC's most hated rival, then make the player watch as the rival was vaulted to power. This is an interesting series of items, and I hope you continue them.