Hi, I'm Julian. Since you have already done some troubleshooting, let's check a few more things:
- Is the phone showing as "allowed devices" in bluetooth and not just discovered?
- Does this happen with all connections like wifi and mobile data?
- Also make sure that the same Microsoft account is signed in on your PC and on the "link to Windows settings".
- Please clear the cache and data of the Link to Window app on your phone before reinstalling.
For more info and guide regarding this, please click here https://support.microsoft.com/en-us/topic/troubleshooting-the-phone-link-82b6c6aa-544e-d4af-fd5d-2629a2a95835.