I personally know of no way of doing this in Paint. Maybe one of the other respondents can find a way. The Kodak Imager program which used to come with Win9x/ME and which can be ported to XP has exactly the option you want by clicking a single box. It will nicely fit any print image to whatever paper size you have and you can select portrait or landscape orientations.
I personally use the wonderful freeware program IrfanView v3.98 to do this amongst other things. IrfanView will even do both a horizontal and a vertical panorama from a list of picture files. More to follow as time permits. Currently there is a real time interrupt to service.