@Setanta,
They didn't have kings but a kind of 'chief'.
In my region (Westphalia) we had had between 300 and 800 a kind of multi-cultural countryside: Franks, Saxons, plus Frisians, Thuringians and Goths.
All lived more or less peaceful side on side (with changing majorities between the Franks and Saxons).
Tombs/grave fields show that quite a few "princes" were here.
With the dominance of the Franks of the Franks after 800, indeed a lot changed which can be seen even today: the land use and the borders of towns/cities (following parish boundaries)
One of the largest territories of a Frankish earl was that of the Earl of Werl (later named Earl of Arnsberg): stretching from south of the Ruhr river to the German Sea.