I recently encountered this problem for a client and the cause had me stumped. I did all the basic checking
1. Check the UPS was up to date
2. Made sure that the Workflow Manager was correctly installed
3. Made sure that the firewall was not blocking the WF manager port (12290 or 12291).
The problem (it seems) comes from Document Library 'Advance Settings'; the document library had 'require checkout' set. I did not think anything of it, but once I removed it the workflow executed as expected.
Its a strange behaviour but at least its something to look at when trying to resolve the issue.