It sounds like you have not configured the payment process correctly. I assume you installed a Google payment module and a paypal module.
Yes :-) Lots of posts and fixes for this.
You need to decide how you want it to work, charging the CC after the fact is going to mean you need to conform to PCI DSS since you are to need to hold the Card Holder Details.
I don't believe VM does this by default and would need a bit of hackery to make it work. Customer orders, Customer fills in details, you 'do stuff', set order to shipping, Customer is charged, Goods are shipped.
Far easier to take the money and then 'do stuff' and ship.