Good question

Well there was an evil in Terminia that was called Majora and it did I guess 'plauge the land' and the elders there sealed the evil into a mask, and since then it has been called Majora's Mask. Then after a long time the Happy Mask Salesman found it since the evil was not gaurded by the ancient race of people.
I guess that Termina had not heard of the hero since they had problems of their own. Also they would not have heard of it since Ganondorf had only conquered Hyrule at that time, he was not able to control the world since he had to deal with Link.
I believe your theory of walking from Hyrule to Termina, but I think it might take a longer time that's why Link took Epona.
That's the best answer I can give you now, but you should see what other people think.