Answer #1 would be: You can change Liferay's translation, but that would hit all occurrences of Next/Previous
Answer #2: It's probably referencing this translation key in every single instance of the templates, so you can override the templates to reference other translations
Answer #3: It might be coming from JSP-Taglibraries, which might be another alternative to tweak.
Which one of these is the right way to attack it? "It depends" (TM)
What does it depend on? The thoroughness that you want to make this change - hit everything, hit the most important parts, how is it implemented in all of the parts that you'd like to change. Also, pay attention to future maintainability, e.g. if you want to carry your changes into the future, you shouldn't make too many detailed changes in different places - or be prepared to repeat them with the next update, even a minor security patch.
Oh, and speaking of updates: The way it's currrently implemented also depends on the version you're running. Liferay's implementation is now preferring freemarker over velocity for templating, so your mention of velocity sounds like you're referring to an old version
