I struggled with a similar problem recently. You can use osslsigncode to sign Windows binaries from Linux. It is also possible, with some pissing about, to get everything to work hands off.

In the end we went with Digicert Keylocker to handle the signing, using their CLI tool which we can run on Linux. For our product we generate binaries on the fly when requested and then sign them, and it's all done automatically.