Much internet research later, I stumbled onto the one possible solution which DID FIX THE PROBLEM for me:
Control Panel -> Internet Options -> Connections tab -> LAN settings button ->
==> be sure that "automatically detect settings" IS CHECKED!!
Somehow, this was not checked for me. Don't know when or how or why that happened. But immediately after CHECKING this option, sure enough I was now able to successfully launch and connect to Microsoft Store.
Interestingly, I had also been having no success logging into my Microsoft account from Windows (I had instead been signing into Windows with a "local account" which still worked). But sure enough once CHECKING this option immediately I was now successfully able to log into Windows through my Microsoft account.