This is the process I followed (without removing Windows Update) which worked in my instance:
Removed users profile (Users\AppData\Local\Microsoft\Edge) by deleting 'User Data' Folder
Launched MS Edge and signed-in with users account, same issue.
Tested under InPrivate Window, no issues encountered although this isn't a viable solution.
Opened New 'normal' window, signed user out of their profile and tested, user can access Company SharePoint. Signed User back into their profile, no issues encountered, likewise after restarting MS Edge.
Hope this helps.
Update: As per another comment (Jonny Sharp), it may not be necessary to delete User Data folder, signing out/in Users Profile may be sufficient.