My experience:
1) ebay: Contact via the hard-to-find contact point for defunct hardware 2FA keys, (thing lasted about 10 years). Result: They removed 2FA without even verifying I was the owner of the account.
2) CoinJar (Crypto): Wanted to disable 2FA by removing authorised devices in their app because I had changed phones and forgot to backup their app data before doing a factory reset. Result: Had to contact them via email and get them to remove defunct phones from my account so I could add valid ones, (couldn't log into the account via web until I did), they wanted to know all contact details, etc, etc - plus since in Australia they require Drivers Licence, Passport, or something similar before you could trade I could also give them that info.
3) Namecheap: Wanted to disable the 2FA that originally used their own app, (I'd swapped phone and the 'fingerprint' had changed), so I could use Authenticator instead. Result: They wanted to know everything: contact details, what the last transaction was and what means/card was used to pay for it, etc, etc ... then they removed 2FA.
All-in-all, just use their contact info and see how far you get, if you can provide details of the account with maybe a transaction or two ... you may get lucky.
FWIW, besides Authenticator, the 2FA tokens are now also added to KeePass, (by way of the Tray TOTP plugin), which gives me multiple redundancies, (synced across all computers/laptops/Androids), and covers all the usual 6 character 2FA plus PayPal 2FA and Steam 2FA.
The Authenticator dBase is also backed up, (requires root though).