call paypal and request a chargeback even if its sent as a gift you can still recover it. I think you used your credit card to fund your paypal right? Then, yes you can call your credit card company and request a chargeback
Yes, I paid using Paypal, but I didn't have funds on the PayPal account itself, so PayPal used the money from the credit card. Are you sure it's possible to solve the problem by calling the credit card issuer? It's too easy.
If you lay out the situation clearly, then yes, it's very possible. Some credit card companies do chargebacks without any apparent reason as well, which is why credit cards are avoided over here on the forum. You should have a good chance at getting your money back.