Anything above 400w will certainly work. The recommendation of minimum 400w for that card is dependent upon other devices in the system. The price difference between a 400w and a 600w is insignificant and worth the extra for the extra power.
Example: Between a decent 400W and 575W
COOLMAX CA-400 400W ATX v2.01 Power Supply -$21.99
LOGISYS Computer PS575XBK 575W ATX12V - $24.99
I don't believe that Video Card needs a PCIe power cable. But if your going to get a new Power Supply I would get one that has one, in case you upgrade the video card later and it is required.
I would also get one that has the highest amperage on the +12v rail, as this is what powers the video card.
If you look at the Logisys one above for an example it has:
+3.3V@38A, +5V@40A,
+12V@25A, -12V@0.8A, +5VSB@2.0A
+12V @ 25A is the important one.
Also depends on your budget...