Do I need >5V power supply to adequately protect against overvoltage >5V? Seems contradictory
Zener diodes are used in the reverse direction and have a specific breakdown voltage, eg a 5.1V Zener will start taking significant current at 5.1V, not 0.6V.
However, they have limited accuracy and a finite slope. They don't prevent a higher voltage across the, they just take an ever increasing current at higher voltages.
Back to the main question.
Whether an over-voltage protection is needed depends upon the particular scenario.
For your case you could put zener and a series polyfuse (zener after the polyfuse). The zener would also protect against reverse polarity as it would conduct in the forward direction. The polyfuse would protect the zener.
Be aware that the Polyfuse will drop some voltage so there will be  bit less than 5V at your circuit.