Dodecahedron, I couldn't figure out an easy one-step method to do it with Flexible Renamer. I got close, but kept running into the infamous string/number sorting problem: when sorting string representations of numbers, sorting is done by most siginficant digit rather than least. For example, 10, 11, 12, 100, 101, 102, 1000, etc. all come before 2 when sorted as strings. (That's why I try to pre-pend leading zeros when naming files.) I did come up with a method for doing it in multiple passes, but that is too much work.
A better alternative is the 1-4a Rename
program you found. It works great for your application. Just check the "Replace" box, leave the top box under "Replace" blank, and type "page$" in the lower box. "page" is the base name you said you wanted to use, while "$" indicates 'number the files consecutively, using at least one digit'. ($$ would be two digits - 01, 02, 03, $$$ would be three digits - 001, 002, 003, etc.) It should look like this:
I think Flexible Renamer is more flexible and powerful in general since it has full regular expression pattern matching capabilities, but 1-4a Rename has its own strengths. Different tools for different jobs...
Thanks for telling us about 1-4a Rename. By the way, 1-4a Rename is emailware - free to use, but the author requests an email acknowledging your use of it.