Recently, Apple Pay stopped working on both my iPhone 13 and my Apple Watch Series 6, with multiple cards, at multiple stores. This leads me to believe it's a software (not hardware) issue. The stores' payment terminals had no issue with tap-to-pay using a physical card, so it doesn't seem to be an issue with the terminals or payment infrastructure at large. Apple wasn't having any availability issues with Apple Pay when I checked its status page at the time either.
Removing and re-adding the cards didn't fix the issues, and neither did a reboot. There were no outstanding updates for either device, and they had last worked for Apple Pay after I had last updated them, so an update hadn't affected its functionality.
Is there anything else I can troubleshoot on the software side to try and resolve this before taking it to an authorized repair store for hardware testing? I really don't think it's a hardware issue, given that both devices' Apple Pay stopped working around the same time, and their Pay functionality isn't tied to each other. Apple Support confirmed there was no block on my account, and my card providers confirmed my cards are in good standing.