It varies a bit with when and where, but if we limit ourselves to the area under the catholic church, a Sovereign Ruler (King, Emperor) could create Duchies and other lower vassal regions in his realm and raise nobility from lower ranks to higher as reward for faithful service or as part of a treaty. Duchies often existed as an extension of various petty Kingdoms, Principalities and Chiefdoms during the early medieval age. The Roman military rank Dux became the basis of the title Duke and petty kings or military commanders of the Franks, Burgundians or Vandals would carve out their own fiefs out of Roman territory and start using a title.

As for King, it is a bit more complicated. Most Kingdoms held a long tradition back towards the end of the Roman Empire of calling themselves Kingdoms and having a ruler calling himself King. Such was the case with England, Scotland, France, Leon (later Castile), Bohemia, Sweden, Norway and Denmark. Others became Kingdoms only after either defeating their theoretical liege Lord and with Papal and/or Imperial approval (such as Portugal) or with Imperial and Papal approval (such as Hungary).

There were only two Kingdoms created in catholic Europe during the medieval period (Portugal and Hungary) and both were given their crowns after requesting them by the pope.