Finally I got the app working again. As it turns out, the app looks completely different now, so there must have been a software update that didn't go through automatically or properly. I had to reset the app on my PC. This advice came from the Windows Store Apps troubleshooter. You can find the details here:
https://www.thewindowsclub.com/your-phone-app-not-working-or-will-not-open-on-windows-10
You do not really need this troubleshooter, but you can go directly to apps (Win+I), find Windows Phone Link and choose advanced settings.