The secret to success was to go to my PCs “Settings -> Apps -> Smartphone-Link app” and there to “Reset the app (loose all app data on the PC)” (not: “Repair” because that preserved the data).
If this would not have worked, I would have tried to re-install the Phone-Link app on my PC because this was another solution recommended here in the MS forum.
Thank you so much for this tip! I followed the instructions and was finally able to re-establish a link between the app on my laptop and my phone.