On my Hostbill, paypal payment is working without problems.
Making sure your paypal payment configuration is correct.
Try uncheck Verify PayPal email, ensure Skip email/business verification and Accept callbacks with HTTP 500 verify error is checked.
Try turn on Disable Explicit TLS.