Are you using any apps that may spoof or modify anything with the Android software (fake gps location apps, something that adds quick settings to your notification bar, Screen temperature modification apps, NFC Tag writer/reader apps, etc)? Considering your phone isnt rooted and the bootloader isnt unlocked im just throwing suggestions out there, but maybe something like this is causing android pay to throw an error?
As much as you may not like it, a factory reset may be the best way for you to know for sure. Your other option is to get a new device and since you would have to set up everything with a new device anyway you mine as well just do it if you can't narrow the issue down. Just make sure you try an NFC payment before you start setting your phone up again.