Wow, I’m getting great info while doing very little work myself! Thanks!
From that link:
So, a similar earlier melody in a hymnal in the German city of Mainz in 1712 then the familiar melody in a hymnal in the city of Hildesheim in 1736. I followed the link on that page to the German wiki page for Gegrüßet seist du, Königin- the original German version. Looks like the song skipped over the U.K. to make it’s first appearance in the English language in America.