Yes, one of my favorite hosts: BlueHost offers payment through PayPal: Its $6.95 per month and includes about everything you could ask for. Homestead is another one with $4.99 the first 3 months and you can get a cheap domain as well. You can log into your paypal account and choose to use a virtual credit card and it will give you a one time use mastercard number and it works like a credit card but it is a paypal payment. I have done this before and works great, another that accepts paypal direct is Hostgator, They will let you host unlimited domains for only $10 per month.
If your paypal is not yet verified, write to customer support team and explain your situation. most hosting companies will reconsider your situation. good luck.
For reasonable prices & quality I can recommend netrackservers. I dont know about paypal though , just check with them.