Turns out it's easy:
- Go to File > Page Setup.
- Click the "Paper Size" dropdown and choose A4 (or whatever default paper size you want).
- Click the "Settings" dropdown and choose "Save as Default".
MS Word had a different way of doing this, so it made it difficult for me to find out how Pages did it. Now that I know the right way, the Word way of changing the default paper setting seems more complicated.