I am in the exact same boat.
All of our orders are processed via PayPal and no new order notifications come through. I am 99% certain everything is set up correctly, and test notifications work just fine.
From the post above, it sounds like maybe there is a problem with the paypal payment processing logic not triggering the new order notification. I do get new order notifications from WC, so that part works fine – just never anything via pushover.
-Mark