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?