Yes, that was it for me. On my test server, which is Windows Server 2008r2, I uninstalled patch kb4056894 and was able to start the publishing service again and publish a test service. Thanks for your help, folks. I'll rollback from production server and wait for a fix from Esri on ArcGIS Server 10.4.1.