It might be helpful to take a corpus-based approach. As a corpus, I have a book from 1904 which reproduces the congratulations sent by heads of state in 1902 to the first President of Cuba. The styles of the various European monarchs challenge some of the suggestions made in other answers in this thread. The letters are written in various languages, but as has been mentioned in other answers there's some common ground between European nations on the terms.
Wilhelm, von Gottes Gnaden DeutscherKaiser [Emperor], König [King] von Preuken, etc: etc: etc:
Franciscus Josephus Primus Austriae Imperator [Emperor], Bohemiae Rex [King] de et Apostolius Rex [Apostolic King] Hungariae
Ferdinand 1ª Prince de Bulgarie
Au nom du Roi [King], Christian Prince de Danemark Régent
Don Alfonso XIII, por la gracia de Dios y la Constitución Rey [King] de España
Edward, by the Grace of God, of the United Kingdom of Great Britain and Ireland and of the British Dominions beyond the Seas King, Defender of the Faith, Emperor of India, &c., &c., &c.
George 1er Roi [King] des Hellenes
Vittorio Emanuele III, per grazia de Dio e per volontà della Nazione Re [King] d'Italia
Nicolas Ier Prince de Monténégro
Wilhelmina, bÿ de gratie Gods, Koninginder [Queen] Nederlanden, Prinses [Princess] van Oranje-Nassau, enz., enz. enz.
Dom Carlos por Graça de Deus, Rei [King] de Portugal e dos Algarves, d'Aquem e d'Alem Mar em Africa Senhor [Lord] de Guiné e da Conquista Navegação e Commercio da Ethiopia Arabia, Persia e da India, etc.
Alexandre I. Roi [King] de Serbie
Oscar, med Guds Nade Sveriges, Norges, Gotes och Vendes Konung [King]
I've skipped one, for brevity and to save transcribing the Cyrillic: Nikolai II of Russia's style can be summarised as: Emperor and Autocrat of all the Russias, of Moscow, Kiev, and a couple of other cities, Tsar of 6 cities/regions/countries, Lord of Pleskov, Grand Duke of five cities/regions/countries, Duke of 11 named places and "others", and we're only half-way through (see note 3).
The first thing which strikes me, and which is consistent with the observation that empires are the result of expansion which engulfs other kingdoms, is that all of the "Emperors" (Wilhelm, Franz Joseph, Edward, Nikolai) also call themselves kings of specific territories. For example, Hungary was part of what we would call the Austro-Hungarian Empire, but its relationship with its ruler was defined in terms of the (historically significant and unique title) Apostolic Majesty rather than the Empire.
The second thing to note is that the four empires were all hereditary, which stands in stark contradiction to some of the assertions made in other answers.
The third point of interest are the principalities. In the case of Bulgaria, which might seem surprising (it's a fairly large place, after all), this is explained by being a vassal of the Ottoman Empire, and it became a Kingdom when it declared its independence in 1908. Denmark is the one which really sparks my curiosity: why did the king style himself a prince?
One common factor of the empires is that they were large and that they included an almagamation of previously independent states. But the same is true of at least two of the kingdoms: Spain (I've seen plenty of references on monuments to Rex Hispaniorum - King of the Spains; and if he wanted to push it then Alfonso could have had a list to rival Nikolai's); and Italy (only recently unified). Both of those kings use a single title in their style, and they're the only monarchs to attribute their rule to something more than the grace of God. The inference can be made that they're intentionally emphasising the unity of their domains and their link with the common people.
In short, an attempt to reduce the distinction between a king and an emperor to a simple criterion seems likely to fail. It seems to be largely a question of historical continuity, politics, and etiquette.