Generally, such kingdoms are formed through the support and affirmation of the Roman Papacy followed by an approved coronation by a local prelate. For example, the Prince Levon II leveraged the assistance he had given to traveling groups of crusaders to secure the papacy's blessing in elevating his principality to a kingdom in the early 1190s. He consummated this relationship with a full coronation ritual at his local cathedral in 1199, and thus the Kingdom of Cicilian Armenia sprang forth atop an already existing lordship.

But, this difference—between kingdom and not—is largely subjective, reflecting status and recognition in the eyes of contemporaries rather than actual possession of territory. Someone could take a title as a means of expressing ambition or claiming legitimacy, but that doesn't mean people would recognize that title. The Emperor Frederick II claimed the title of King of Jerusalem for his son, despite the fact that the small child, Conradian, neither possessed any land nor had he visited the kingdom. When Frederick announced this to the local lords of the Latin East during his visit in the late 1220s, the reception was dubious at best: they local lords, led by the Ibelin family, seem to accept his title to the crown but reject his ability to compel them to give up positions they believe to be theirs. Upon his departure, open conflict erupted between the local nobility and the Emperor's representatives.

Also, plenty of dukes, counts, and other titled nobility often equaled or surpassed kings in wealth, power, and status. The Counts of Champagne easily rivaled the Capetians of the early twelfth century. The twelfth-century text of Suger's Deeds of Louis the Fat is essentially chapter after chapter of King Louis VI riding around suppressing local, rival lords through violence. This isn't because Louis was a particularly quarrelsome individual—although, who knows—, but rather because local lords at times felt willing and able to pursue their rights and privileges in opposition to the King. Sometimes they were even successful.

I don't know why in the Lithuanian example the successor didn't declare himself king, but he may have been unable to secure a coronation ritual, which is rather central to anyone claiming to be king. Calling Lithuanian historians!

Edit: words in the second paragraph did not make sense. i fixed those words.