If you Foxit Reader installed, this might be the culprit. Open any workbook in Excel then go to File -> Options and select the Add-ins tab (as of Excel 2016 may vary). At the bottom of the Window it says Manage; select COM Add-ins from the drop down menu and click Go. Untick the Foxit Reader Add-in apply, ok and exit. This has resolved my issue and I found the relevant information on this website (it was related with Remote Procedure Calls):
https://superuser.com/questions/1124945/excel-interop-remote-procedure-…
Although the problem is not exacty the same, I think this information might be relevant since add-ins might be causing the issue. It is also worth checking if RPC is working from Windows Services. The error I got before disabling the add-in is below:
Internal : Could not execute code stage because exception thrown by code stage: The remote procedure call failed. (Exception from HRESULT: 0x800706BE)