I ran into the problem on my brand new Surface Book - and looked and tried everything and stumbled across both a work around, a permanent solution, and at least one root cause:
WORKAROUND: If you're experienced with Regedit.exe (and I would really recommend before you try anything you make a backup copy of your registry), you can search through the registry and delete *every single instance* of the keys associated with the App ID. If you're not sure what an AppID or a registry key is, don't try this method as you can do serious damage to your machine.
If you are pretty comfortable, you'll find that once you delete every instance of the app ID and associated keys from the registry (you may have to "take ownership" of certain registry key containers to do this, immediately the app will download.
However, it's only a workaround because it does address the root problem. Also there are dozens and dozens of appID registry entries per app and it takes forever... and on the next app update, the you'll have to do the whole thing again making it not really the ideal approach.
THE PROBLEM:
Because I figured out the workaround, I assumed that something during the Store Download process was corrupting the registry entries. There are a number of ways this can happen, but typically it has to do with a third party agent "packet sniffing" your WiFi network adapter.
There are a number of applications (including antivirus) that legitimately have a purpose to do that, so this is where you should start investigating on your computer: Anything client on your PC that may have access to scanning, sniffing, or proxying your network adapter.
MY SOLUTION:
In my case it wasn't a network adapter at all. I use "Hyper-V" to run virtual machines to do development without mucking up my Surfacebook. I'd enabled hyper-V and in order to give my virtual machines internet access, I set up a virtual network adapter and tethered it to my physical network adapter.
As it turns out - even if your virtual machines are turned off, even if they are unattatched, the mere *presence* of the virtual network adapter in hyper-V does some strange proxying of all the downloads on your physical machine: In my case, it was somehow corrupting the registry process when the Windows Store on my physical machine was trying to update.
I turned off the virtual machines, removed the WiFi virtual adapters, then deleted the virtual adapter from each virtual machine configuration, and rebooted my machine: immediately every store application downloaded and installed without problems.
I chased this for months and months with no success until the above. I hope this helps one of you, or at least helps you pinpoint on your machine exactly what is happening.