OK, so it was my mistake reinstalling Norton on one machine but why does Norton prompt to allow the Windows Store app?
I have no interest in micro-managing my security, that's Norton's job. If I wanted to see these prompts I would use a certain AV and firewall + HIPS combination.
It is Microsoft's Store, strewth! I opened it, it is not malicious, allow it!
Thankfully my other two machines do not have Norton and do not bug me like this.