Well, I haven't done any real checking on this, but I would expect that Kaiser entered the Germanic languages pretty early on and stayed there. After all, most of the tribes that made linguistic contributions to modern German interacted with the western empire at some point before its collapse. The term may or may not have been used by the Lombards, Franks, Goths and so on, but Charlemagne certainly called himself Kaiser, as did all of his successors. Whether this was a survival or a reintroduction raises the question of the pronunciation of Caesar in the Latin of the 8th/9th centuries, but that's way outside our brief.