Just to get the dumb question out of the way. Do you have installing SelfService Automatically enabled? As a temp work around you could package the app, and deploy with a policy.

I forgot to specify but yes, I do have this option checked and I've tried to check/uncheck it to "force" deployment but without success.

Assuming the Jamf Binary is installing, can you run any policy that delivers a package? Self Service comes down as a package as the device is enrolled, if there is an issue reaching the Distribution Point Self Service won't install.

I've just done some tests, I can deploy apps via the JAMF server and via App Store directly without any problem.

Are you deploying self service to computers or devices? or both? 

Only on Computers.
In the meantime, I've created a workaround that deploys the Self Service package, but it's not as clean as the native solution.