I know this is an old post, but here's how I fixed it:
Go to play store menu > account > payment methods. Remove Verizon wireless as a payment method. I had to do this with three items.
Under App manager on phone, clear cache and data in play store. Clear cache in Google Play Services.
Next time you select payment options when purchasing an app it should show "set up Verizon Wireless billing" or something now.