> Is the phone number a mobile number registered in a telephone contract in a name that matches that on your PayPal account?
Yes, it's the same number.
> Does your telephone service provider accept short code messaging?
Yes, I use plenty of other services that are configured and use two-factor authorization to that phone number. SMS messages from them are always received.
When you add (or change) the phone number to your account it looks like this in the end - 8 7xx xxx xxxx. Then when you want to set up the 2FA the Paypal tries to send the SMS to the phone number like this - +7 8 7xx xx xxxx. As you can see the extra +7 is prepended and IMO it's the main problem.
I tried to enter the phone number in these formats: 7xx xxx xxxx and 8 7xx xxx xxxx. Neither works. +7 is always prepended and the final phone number looks like this - +7 8 7xx xx xxxx.
When you try to enter +7 when setting up the phone number the Paypal mobile app strips (ignores) the plus (+) sign. Therefore you can't setup the phone number like this - +7 7xx xxx xxxx. When you try to do the same from the web the Paypal says that the phone number is incorrect - "You have entered an invalid phone number.".
I hope that helps to narrow down the problem.
