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.
I already asked PayPal for refund, but I will call the Bank. They should be faster. Plus, I don't think that PayPal want to solve the problem, since I send the money as gift, not paid for goods.