Summing up: 1) BIOS/iDRAC/PSU firmware update ... same alert2) Replaced the 495Ws by 750Ws... It works as expected after a couple of re-boots. No alerts. Will see.    
Hello,  The server - R620 - is old enough. No issues since ... .   We have started to receive "Power required exceeds PSU wattage" alert during the server re-booting only (!)  once or twice a month. No alerts between re-bootings. The PSUs (2*495W) are Okay and not overloaded at all (about 50%).  What can be tested/investigated/fixed? Thanks for the prompt reply!  
R620 ... Started to receive Power required exceeds PSU wattage