Earworm is a calque, a word built by translating each piece of a foreign word. The German is Ohrwurm: Ohr, "ear," plus Wurm, "worm." English simply swapped in its own words for each half.
The German word did not start as a metaphor about music. Ohrwurm is also the German name for the earwig, the insect. The idea is old and widespread. Etymonline notes that the English earwig comes from Old English earwicga, "ear insect," and reflects a long-held but false belief that the insect crawls into people's ears. French has the same idea in perce-oreille, "ear-piercer."
From there the step to a tune is short. A song that burrows into your head and refuses to leave behaves a lot like a creature that has crawled into your ear. German speakers applied Ohrwurm to a catchy melody, and the sense is reported as a loan translation in dictionaries.
English already had its own earworm for animals. Dictionary.com dates the pest sense, as in the corn earworm, to the 1880s. Word Histories finds an earlier use in 1598 meaning an earwig, possibly translated from Dutch oorwurm. Neither has anything to do with music.
The musical sense arrived much later, and sources disagree on the first date. Wikipedia gives Desmond Bagley's 1978 novel Flyaway, where the author points out the German origin. Dictionary.com says 1980 to 1985, and Word Histories finds 1982 in a linguist's writing on poems. The word was probably a rare import for some years before it caught on.
It has since become a verb as well: Dictionary.com lists "to earworm," meaning to work its way into someone's mind.
The worm half has deep roots. English worm and Old English wyrm go back to Proto-Germanic wurmiz, the same word behind German Wurm. So the modern idiom is a true cousin, not a coincidence: German and English reached for the same creature, with the same name, to describe a song that will not let go.