So, I’ve been locked out of my PayPal account because I was using Multi-Factor Authentication (MFA) with Google Authenticator codes.
After I changed my phone I noticed that (1) on the new phone, Google Authenticator was empty and (2) there was no way to log in to PayPal without the Google Authenticator codes:

The PayPal call center is unable to help me for the moment.
There are multiple take-aways from this, and probably the most important is to use an authenticator app that backs up the accounts in the cloud. Google Authenticator doesn’t do this. Authy does.