Two monolingual dictionaries available online say 遥か can be used adverbially as well as adjectivally.
Similar words include 結構, 色々, 十分, 大変, かなり, 相当, and 特別. As you can see, most of these are intensifiers.
- 大変な事件。 (na-adj.) ／ 大変おいしい。 (adv.)
- 特別なプレゼント。 (na-adj.) ／ 今日は特別寒い。 (adv.)
I think similar things happen commonly also in English ("fast", "long", "enough", etc. can work adverbially without "-ly").
EDIT: 彼方 itself works both as a na-adjective and a noun, so it can be modified both by an adverb and a normal adjecitive. 遥か彼方, 遙かな彼方, 遠い彼方, 遠く彼方, とても彼方 are all valid. The same thing can be said for 昔, which can be modified both by an adverb and an adjective (遥か昔, 遙かな昔, かなり昔, かなりな昔, 遠い昔, とても昔, ...)