Yeah, as Robin said, you need to wait for the money to transfer into your paypal account balance BEFORE you make a purchase.
With that, there's not much you can do.
What happens is paypal will take the money from your account within 1-2 days of you putting in the request, but will take the additional 2-6 days (depending on where you live) to transfer in, as it's going through processing. That is why the bank said that paypal already took the funds. Because they had. You just didn't have access to them.
I'm sure you knew that, right?