When a character reaches the King tier, is he still expected to clear hexes himself in order to expand his domain? Or does his vassals (henchmen) do this? Or their henchmen? Or hired adventurers?
For wilderness humanoid lairs of the village type, the King can simply send his army to smash them. But would the army be effective against the lairs of monsters of a higher level?
This is why you make “Marcher Lords” out of high-level heroes/adventurers: as rewards for their deeds, you grant them wilderness hexes at the edges of your domain as marches, and they have the responibility to clear them out, but they receive your approval (i.e. they get to do that without you then sending an army to knock their unfinished keep over and take the hex) and support etc.
I don’t imagine any king clears his own hexes; he’s got too many vassals and sub-vassals and sub-sub-vassals and so on to bother.
So, the King offers rulership (and noble title!), as a vassal of course, over any hex to whoever clears it. NPC kings should do so as well…
An alternative would be to send the royal army to clear territory, possibly with PC-class “special forces” for cleansing non-humanoid monster lairs.
By the way, how did the Kings of Spain organize the Conquistadores?
By contract. The expedition leader would negotiate and sign a capitulacione with a representative of the Crown whereby the leader would raise a force and transport it at his own expense, to conquer a specific area of land in a specific period of time. If this was accomplished, the expedition leader would be granted rights to the land, with no taxes owed to the Crown for a negotiated length of time. Most of the leaders were younger sons from hidalgo families, so there was a martial tradition and some seed money available, but they weren’t heirs who might be missed if they failed.
Similarly, England substantially used Royal Charters to explore and eventually colonize the New World (as well as open trade routes with other parts of the world). These charters were much like corporations with the Crown as the lone stockholder. Notably, “cheating” this stockholder of any duly earned profit was treason, punishable by death.