I spent 3 hours following every rabbit trail suggestion, then 2hrs with the first MS support) on this issue. I did everything, including resetting my computer. PAINFUL!!
FINALLY, the 3rd MS support tech had me SIMPLY reset my region to the US (I live in Puerto Rico and it defaulted to PR). Once I reset the region (Settings-Time & Language-Language & region), rebooted and now the Microsoft Store downloads! IT WORKED!!
Just to test the solution, I reset the region back to PR, and the Store would not download (Try Again Later Message). So back to the good old US setting and....NO PROBLEMS
They also suggested that I reset the time to EST, because he said that could also be an issue, but that wasn't the real solution for me. Hey, give it a try though.