I recently had to do this, but for like 37 different apps. I had to contact Google customer support, and they reset the device setting for me, letting me re-register with my new device. Pain, but it worked once they did their part.
Ah, definitely not a fun experience. For those who utilize 2FA, I recommend generating backup codes (link to Google documentation).
These are static, one-time use, codes that you can use in place of the Google Authenticator app.
(Caveat: if you download a set of backup codes, treat this with as much confidentiality as you would a credit card number. Don’t store them - physically or digitally - in an obvious place).