"Edit in Office" macro not working

Customer is unable to edit / open document via "Edit in Office" macro. An error message (please see screenshot attached) is displayed. I have also added other screenshots with additional information from their Windows Event log.
The customer has tried using different web browsers (IE, Firefox, Chrome).
We also thought it might be a communication error between Windows 8 and Office 2013 (as described here: http://blogs.technet.com/b/office_integration__sharepoint/archive/2015/04/20/office-2013-error-quot-certificate-error-the-application-experienced-an-internal-error-loading-the-ssl-libraries-quot-when-opening-files.aspx), but that was not the case.
Do let us know what additional info would you need.
Best regards,
Margaret