I have UK and Italian credit cards. Italy also has 5 digit postal codes and I've sometimes been able to use the postal code at the pump with an Italian card.
I've also called my credit card company and asked if I could put a temporary address on a credit card so that I could have a zip code associated. In my case they said I would have to have that as my only address but could change it back later. In the end I decided not to do that, but might be worth asking if your credit card company can do it. Perhaps just put the address of the hotel you're staying at.
As other people have said, I've also had luck using just the digits of my UK postal code padded with zeroes. I've never been able to use all zeroes.
The mechanism that the gas station uses, is the credit card Address Verification Service. It's worth noting that there seem to be restrictions on this in various US states as noted in this cpn site:
There are some controversies and legal issues when requesting AVS
information. For example, in California and Massachusetts it may be
illegal to ask for ZIP code information, as this is seen as a privacy
violation.
This may explain why all zeroes are accepted in some places and not others.
AVS works differently with different card suppliers, so it may be possible that a Mastercard works with a foreign 5 digit postal code, or zero-padded postal code, whereas an Amex doesn't, or vice versa.