In a second step, you would then enlage the page size to e.g. letter again, but this time you can specify where you wan to add the additional space. This is done in the crop dialog, but can also be done via a preflight profile.
And finally, you would add the Bates stamp on the now modified page.
This is a lot of work, but some of it can be automated. I would recommend you run through these steps once manually to see if the output is worth the effort, and then potentially think about automating the steps.
I was able to eliminate a step, though, and reduce the process to just a couple of clicks.
Your tutorial put me on the right track -- I never would have thought to use Preflight without it.
But rather than creating a fixup to "scale page," I used the option to "scale page content." This reduces the size of the page to the percentage specified, but leaves the page on the original size sheet. I know I'm not explaining this well -- it treats the whole page as an image (without actually converting it to an image), and reduces the size of that image on the page. The page size is not changed.
So I saved that fixup, and now I can run it as needed.