Actually, my good sir, that is very simple to figure out. Wikipedia says that A4 paper is 210×297 mm. Let's convert that to centimeters, 21x29.7 cm. Now go into Paint.NET, and simply insert those numbers in the "Print Size" box.
And Paint.NET outputs: 794 x 1123 px (That's the default of course).
To anyone else: If I am wrong, please do correct me.