Anybody know how to create a custom policy to deny public network access to PaaS services

MarxAndreas and Roberto Camacho 

it isn't possible to have a global Policy for public network access to PaaS resources, because each PaaS resource provider has its own (ARM) way of declaring public network access hardening. That's why you have built-in policy definitions to restrict network access for each PaaS resource type.

Regarding the "deny" instead of "audit" question, some policies do have an "effect" parameter you can change at assignment time. I am not sure, however, if this applies to some PaaS network restriction policies. In case you have policies with an hard-coded "audit" effect, you would have to duplicate the built-in definition and create your own custom definition from it.