As ファルキエッレ stated, the particle へ is cognate with the noun, variously spelled 方 or 辺, and probably derives from it. This has been a very productive noun, appearing as a component of many terms in modern Japanese:
- 芦辺 ashibe, "reed-covered bank"
- 海辺 umibe, "seaside"
- 夕べ yūbe, "last night, yesterday evening"
Some modern JA terms aren't necessarily even recognized as compounds:
- 前 mae, "front", compound of 目 + 辺 "eye-wards; visible place"
- 家 ie, "home", probably a compound of 寝 + 辺 "sleeping place"
This へ may also be cognate with 瓮 (he, "container"), from which we get 鍋 nabe, "pot", compound of 肴 + 瓮 "side-dish container".
Regarding the use of へ as a particle meaning something like English "to" or "towards", we already see such usage as long ago as in the Man'yōshū poetry of no later than the mid-700s:
- Poem 3696:
新羅奇敝可 伊敝尓可加反流
Shiraki he ka / Ihe ni ka kaheru
I'll go back to Silla [the kingdom in the north of the Korean peninsula] or to home...
Perhaps in reflection of the noun's sense of "place, general area", the particle へ in the ancient texts denoted "towards, in the direction of" rather than denoting a specific arrival location, and was more often used to indicate faraway places rather than anywhere close by. In contrast, に was used to denote a specific arrival location and was used for closer places. The vaguer connotations of へ ("in the direction of a place") still persist to some extent in modern Japanese and contrast with the more specific connotations of に ("specifically to a place").