The only thing that might make sense is something related to Defender or the SmartApp control. Did you make any security setting changes?
Have you reviewed your Application and System eventlogs for strange errors?
Have you done a full Defender scan or ran MSRT (C:\Windows\System32\MRT.exe)?
I going to suggest that you try the "find a friend" solution. You see, I have this neighbor, and every time that he has a problem with his pc he calls me on the phone and tries to explain what it's doing and invariably, I tell him to STOP, STOP. Then I walk down to his house and sit in front of his pc and take a look around at what he's done. I check the event logs, see what programs he has installed, and sometimes run trace tools like Process Monitor.
It's just so much easier to troubleshoot strange errors while right in front of the pc than it is to try to explain to someone; "now type this in, look for xxxxxx".
That's the situation we're in with this problem. This forum works best when a user asks about a problem that we've seen before or can recreate on own machines.
I don't know why your pc would be displaying a Windows Store popup when you try to run certain programs.
Do you know someone who works in either desktop or server support? Ask them to sit down in front of your pc and take a look around. See if you can find someone who has experience running Process Monitor. That's the tool that I would use to try to figure out what your pc is doing. But it takes an experienced admin to be able to look at the capture and figure out what's going on.
https://learn.microsoft.com/en-us/sysinternals/downloads/procmon
@Michael Taylor any thoughts?