Windows Update "cannot connect", and Windows store cannot download apps

So, I have been having issues with Windows 10 Update and Windows Store.

To start, This PC is running Windows 10 Home, which was updated from Windows 8.1.

I don't exactly know when the issues began (I don't often use the windows store, and all updates should be running automatically after hours). However, now when attempting to download a new app, I ran into problems.

Firstly, the error I received when attempting to download an app was this:

Something unexpected happened

Code: 0x80072F8F

I then attempted to "Get Updates" (from the store) to the same effect. I then tried running Windows Update, which gave me a separate issue:

We couldn't connect to the update service. We'll try again later, or you can check now. If it still doesn't work, make sure you're connected to the Internet.

I then went exploring for some solutions: I found a Microsoft Answers article on the Error Code, as well as another Microsoft Answers article about fixing the windows Store, and a TechNet article.

None of these articles have been able to help me fix the issues. In the TechNet article it advised collecting a log of the Update Service, which I have (but is apparently too big to upload - let me know what information I can take from it and post what is relevant).

I also have the Sophos Firewall Hardware, and Sophos Endpoint Antivirus running in the network.

Turn off all of your Firewall and antivirus temporarily.

Run this official Windows Update troubleshooter:

Windows Update Troubleshooter

https://support.microsoft.com/en-sg/help/4027322/windows-windows-update-troubleshooter

Then download the Windows Update again.