Charley,
This is a truly interesting question and one that deserves a lot more thought.
I think most "kings" became kings through strength and dominance over their own country men. Look at the War of the Roses. Both sides claimed to be the true king, but one was superior in battle and in the strength of his army and so became the one king.
After winning by force, most all kings then turned to their various religions, as Robert said, to validate their positions with the protection of their god or gods. It was good PR.
However, as heads of the family, the kings then turned to cementing their position and that of their family by producing an heir. Then they also began to create the trappings of royalty and the grand ceremonies to separate themselves from the "common man".
People supported the new king in order to survive and live in relative peace and harmony and for the protection that having a strong central king would provide them.
As the years went by and either the king left no supportable heir, or their were too many "claimants" because of royal indiscretions, either a battle was again necessary or the people would vote on the person they wanted to be their next king as the boyars did after the Time of Troubles in Russia when they picked young Michael Romanov. And they picked him because he was vaguely related to Anastasia Romanova who was the wife of Ivan the Terrible. Again, the boyars were looking for that touch of previously confirmed "royal Blood".
Once a person became king either through strength of arms or election, the mantle of "royalty" then settled on him. He will still bleed red if stabbed and probably will die like any other man in a combat situation, but an aura of "difference" from ordinary men begins to be perceived around him as that happens both he and his "subjects" begin to accept that aura as "God given". Again good PR.
When, in the early days, having "favor with the gods" was taken much more seriously than it is in our time, the ordinary man would surly follow a person who had that favor. Even if, to us, it was only perceived as the god's favor, to them it was a reality.
I have more thoughts on this, but will stop now to let someone else comment and/or correct me. Again, this is a most interesting topic. Thank you, Charley, for bringing it up.