The parts layout stays the same when you change the paper size or margins (that is to say, the program ignores the page bounds and the XYcoordinate layout of the parts stays the same), so you'll definitely have to reorganize the parts to fit the changed paper size bounds. Like Benton188 mentioned, if you decrease the margins to however large you printer can go, you'll maximize the amount of space you can fit parts on a page.
You can reorganize the parts layout manually in the 2D window. If you're new to Pepakura Designer you could start with the program's automatic recalculation function after you change the paper size, found via the following menu path (at least with Pepakura Designer 4). There are a few variables you can adjust, you'll want it to look something like below but with the dimensions you want.
[2D Menu] > [Recalculate Parts Layout...]
This function is okay but it will space the parts out a lot and some parts might still overlap the page bounds so you'll probably want/need to spend some time moving and rotating the parts manually to ensure everything fits and to minimize wasted space. You can do this using [Select and Move], [Rotate], [Join/Disjoin Face] functions.
Instead of using the automatic recalculation function, it might be easier to just move/rotate parts yourself from the start, it just depends on your preference.
Good luck with your project.