For the sake of testing, toggle the Enable Onepage Checkout in Config > Sales > Checkout to see if the payment methods show up on the two-step checkout.
In my case, the toggle got flipped so that, although Enable Onepage Checkout was set to No, I was getting the One Page Checkout view on the frontend. After flipping the setting, I was able to see all the correct Payment Methods on the second step of the checkout process (as expected).
I'm not exactly sure "how" my checkout toggle got flipped (yes is now no) but I suspect it had something to do with PayPal config settings.
Once your Payment Methods show up then you can start troubleshooting why they don't appear on the One Page Checkout.