You’re thinking about it the wrong way. Whether you are in NTSC or PAL mode, you can import a PSD of any dimensions as a menu. Only on export to DVD will Encore scale the menu the standard NTSC/PAL size (on the DVD itself)
Obviously, your source menu is 720×480. I would propose that you Edit in Photoshop, resize it to 720×576, and then save it. From then on, this menu will be 720×576, avoiding the problem you see when you create a comp from the menu in AE.