For anyone who is still not able to solve this: I found what must be the most un-intuitive solution on Microsoft's site, and it actually worked for me (when none of the above solutions did):
https://support.microsoft.com/en-us...f-i-cannot-download-or-update-apps-from-store
Here are the steps:
On your phone
Check that your phone is set to the correct date and time.
Select Settings > Time and language > Date+time (Lumia with Windows Phone 8: Settings > date+time).
Turn Set date and time automatically to Off, and manually set the current date, time and zone.
Sync your Microsoft account manually and check its status.
Select People > ... > Settings, tap and hold your Microsoft (Outlook) account and select Synchronize (Lumia with Windows Phone 8: Settings > email+accounts, tap and hold Microsoft (Windows Live) account and select sync).
Wait your phone to sync and then continue to the next step. If you get an error, use your browser and try searching online to find a support article for the error code.
Go to Store and check if any app or game remains in the downloading phase without finishing, cancel all the pending downloads, restart your phone and then manually check for app or game update from Store. We recommend that you keep your phone connected to a charger and WiFi network when checking for app updates.
Select Store > Menu > Download and updates (Lumia with Windows Phone 8: Store > ... > downloads), or tap the icon that shows a count of the pending downloads.
If any of them indicates an error, see the details, then tap on it for more details. To delete an app from the queue, tap on the app and tap X to stop the download and remove it from the queue. Lumia with Windows Phone 8: If any of them indicates Attention required, tap on it for more details. To delete an app from the queue, tap and hold it, then select cancel download.
Lumia with Windows 10: Make sure your phone doesn’t have a software update pending by going to Settings > Update & security > Phone update.
Restart your phone and start the manual check for app updates. Go to Store > Menu > Download and updates (Lumia with Windows Phone 8: Store > … > settings, tap check for updates). At the bottom of the screen you will see Check for updates. After checking for updates, select Update all from the top of the screen.
Keep your phone connected to a charger and WiFi network and leave it untouched while it’s attempting to download the app updates.