I do not use MS paint. It is very basic and I believe the default resolution is 92dpi. For printing the final image for most purposes does not need to exceed 300dpi, but 92 is a bit too little. Most software allows you to define the "background" resolution of the sheet so the problem you encounter does not happen. In my case, using Photoshop, I have a blank saved at 300 dpi and size A4. Then just before copying and pasting the image, I ensure the final resolution is 300dpi, keeping the physical size as required. To save paper I usually use 7x5in to get 2 to a page. If you must use MS paint you could reduce the resolution to 92dpi. If I were you I would instead, use the free paint.net where you can do a lot of editing before printing.Have a look at paint.net Create a A4 sheet at 300dpi first then proceed as above using paint.net to change the resolution.
Sony Xperia Z5 review: Hands-on with the phone which the Z3+ should have been