You have proven that travel is an aceptable translation of viaje sometimes. But, does it fitting sometimes mean it fits all the time?
You have to consider both the English and the Spanish, and, in my opinión, "your travel starts/begins here" doesn't sound right in English. Not that my opinión is final, or holds more weight than yours, I just want you to consider that all possible translations of a word don't necessarily fit in every phrase.
Like with "agencia de viajes" - you couldn't translate it "journey agency" even though journey is ok to translate viaje at times.
Anyway, like I said, this is just food for thought. Take it for what you may.
I usually use travel for vacation-related or transportation-related subjects. I don't know what it is defined in the dictionaries.
Journey is more like a process. For example, grade 1 to grade 12 is a journey for students. Students do not travel from grade 1 to grade 12, it just sounds weird.
It should be according to wordreference.com: http://www.wordreference.com/es/translation.asp?tranword=voyage
"Empieza" is conjugated to agree with "viaje" not "tu", because the subject of the sentence is the journey, not you. You can think of it like: "Your journey... it starts here".
It doesn't matter whose journey it is: "Mi viaje empieza aquí"; "Tu viaje empieza aquí"; "Su viaje empieza aquí"; "El viaje de mis padres empieza aquí".