Not sure what the exact issue is, but as you mention you are new to Azure you might be missing some basic information.
Including tables in the Sitecore databases is not a good idea. Let that be clear.
You can however easily create a database for your custom data in the same SQL server instance that is used by the Sitecore databases. There are tutorials on ...
After contacting Sitecore support, it seems that this is caused by a timeout in the Publishing Service which then gets passed through to the CM server.
The fix was:
Extend the timeout on the publishing service configuration
In the /config/sitecore/publishing/sc.publishing.xml, change the <CommandTimeout> element for the <sql-backend-default> ...