Edmund, the song need not have come to Germany from Scotland. Here is what Hamish Henderson (who certainly knew his way round the Italian and German folk song traditions) has to say:

[1986:] [Many] of the narrative songs which were to find their way into Child's 'English and Scottish Popular Ballads' were just as certainly incomers from across the North Sea, or 'land-loupers' which came up from the South, after crossing the English Channel - in some cases starting their fabulous migration in the Mediterranean world.
A revealing example of this latter peregrination is provided by [Lord Randal]. The version printed by Sir Walter Scott in his 'Minstrelsy of the Scottish Border' in 1802 can claim to be one of the two most famous ballad texts in the world (the other is Edward), and generations of Scots poetry lovers have undoubtedly accepted without question the wholly Scottish national identity of this haunting piece. However, the truth is that it is only one version of a very widely diffused international ballad, and that the earliest indication of its presence in a particular culture comes from Italy, where it seems to have been popular 350 years ago. A Veronese broadside of 1629 gives the first three lines of L' Avvelenato (The Poisoned Man), an unmistakable first cousin of Lord Randal [...].
Since then, dozens of versions have been recorded up and down Italy. In Germany 'die Schlangenköchin' (literally, the woman who cooked snakes) is manifestly the same ballad. Although the texts we have are all from the nineteenth century, or later, it is plain that they represent a centuries-old tradition, as do (for example) the Dutch, Swedish, Danish and Hungarian variants. Lord Randal is an 'all-dialogue ballad': that is, the entire action is unfolded through conversation between the protagonists - here a mother, and her son who has been out hunting or courting (or maybe both). (Hamish Henderson, Alias McAlias 82f)