Heraldo é a forma registada por Rebelo Gonçalves no Vocabulário da Lingua Portuguesa, de 1966. Sobre a origem deste nome, transcrevo o que diz José Pedro Machado, no seu Dicionário Onomástico Etimológico da Língua Portuguesa:

«[...] do fr. Hérard (com as var. Héraud, Hérault, etc.), de origem germânica, heri-, var. de hari-, "exército", e hard, "duro, forte". Por vezes aparece escrito, erradamente, Eraldo [...].»

Machado não acolhe a forma Haraldo, que parece simples adaptação do inglês Harald, este, por sua vez, variante escandinava e alemã de Harold (português, Haroldo), de Hereweald, de here, "exército", e weald, "chefe, líder" (cf. Behind the Name).

"Eraldo" é, portanto, forma incorrecta.