I had the same issue with a new site I was launching and testing. Turned out to be a simple mistake, when trying to check out I had no address set, specifically city.
If you enable the PayPal option and enable logging, subsequently attempt a transaction and check the WooCommerce > status > logs – should point you in the right direction.
