A client contacted us because their Office 2016 applications would not open properly. We confirmed the issue and identified error code 1058-4.
After confirming it wasn't an issue with the firewall, we discovered a critical Office service not running. It's called Microsoft Office Click to Run Service and it should be set to startup automatically (and also should be running actively). See below: