This thread doesn't answer my question as principalities weren't under a king who had given them their title and who they owed fealty to. Principalities are top of their own pile.
The original question is wrong in claiming that a principality was an independent state. There have been some independent principalities but the majority of all principalities were dependent states, parts of higher and larger states. And it has often been rather controversial whether a specific principality at a specific time should be considered dependent or independent.
In the Holy Roman Empire the princes were a class that arose by about 1200. A prince or Furst was the first man or ruler in his principality and collectively the princes or Fursten were the first men in the empire. Some of the princes had the title of prince or Furst but others used other titles.
From lowest the highest the titles used by the princes in the Holy Roman Empire were princely count, landgrave, margrave, count palatine, prince, duke, grand duke, and archduke.
And the princes of the empire were all vassals of the emperor, and their principalities were all within the empire, until 1806. There were some independent principalities, duchies, and grand duchies in Italy and Germany after 1806.
[Added 01-26-2020. And in the case of the German princes, dukes, and grand dukes, their states were all only semi independent, Napoleon established the Confederation of the Rhine in 1806 right before the Holy Roman Empire was dissolved, and all the German states except Austria and Prussia eventually joined it. And it was probably Napoleon who awarded higher ranks to various members of the Confederation of the Rhine. All of the surviving German principalities were only semi independent after 1815, being members of the German Confederation established in 1815, and so their rulers couldn't simply promote themselves to higher ranks without consulting the other members of the German Confederation. The German Confederation was dissolved in 1866, but most of its members joined the North German Confederation of 1867 to 1870, and the South German states joined in 1871 when it was transformed into the German Empire. So only the Italian principalities were totally independent states.]
The independent princes, dukes, and grand dukes after 1806 didn't have the power to use any title they wanted to but had to use title awarded or recognized by the other nations of Europe. For example, when the deposed elector and Landgrave of Hesse-Cassel was restored to his throne after the Napoleonic Wars he wanted to take the title of King of the Chatti but the Congress of Vienna only awarded him the title of grand duke, but he continued to use the title of elector. It is claimed that the Congress of Vienna recognized and granted the title of king to rulers who had been electors before 1803 and recognized and granted the title of grand duke to rulers who were made electors in 1803 and some other rulers.
In Russia, Kievian Rus is usually called a principality. But of course there are several possible ways to translate the title of the ruler. The title of the rule was knaiz which is usually translated as duke or prince, but could be translated as king. Kievian Rus was soon divided into several principalities under the authority of the ruler of Kiev itself, who became known as the velikiy knaiz which is usually translated as great or grand prince or duke, but could be translated as great king or grand king.
There were somewhat similar situations in Medieval Lithuania under a ruler usually described as a Grand Duke, and in Medieval Poland which for centuries was divided into several principalities under a senior prince. When Christian rulers used the Latin titles of princeps "prince", dux "duke", magnus dux "grand duke", etc., it is certain that they were not claiming to be kings, but when pre Christian rulers used titles in their native languages it is less certain whether those titles should be translated as prince or king.
Examples of nobles who proclaimed themselves kings include:
In 879 the Frankish noble Boso was elected king of Burgundy or Provence by a a gathering of Nobles.
In 888 Margrave Rudolf was elected king of Burgundy by a group of nobles. The two kingdoms of Burgundy united to form the Kingdom of Arles or Burgundy in 930.
Who was king of Sicily before Roger II? Nobody. Roger II, Count of Calabria and Sicily, was crowned King of Sicily and Italy in 1130.
Count Alphonso of Portugal in the Kingdom of Leon in Spain proclaimed himself King Alphonso on 26 July 1139, and was recognized as king by Alfonso VII of Leon and Castile 5 October 1143 in the Treaty of Zamora, and was recognized as king by the pope in 1179.
I note that in those cases the nobles in question did not simply declare themselves kings but had to do a lot of political effort before and after becoming kings in order to be recognized as kings.
It is possible that experts on European history will think of other examples of nobles making themselves kings.