I believe the issue is with the debit / credit card itself. I suspect it has to do with localization, meaning where you live versus where the company officially sells its software. It could have to do with the debit / credit card company itself following United States protocols and the amount of protection provided.

I had my own issue when trying to purchase MineCraft off the Internet. The hosting company resides in Europe, and I am in the United States. I tried my personal debit card, a gift card, and then even PayPal itself. I think PayPal shares the same limits. Eventually, it became a requirement to visit a local Walmart in order to purchase a registration key.

"International" refers to being based in "Europe" I think. It is possible to get a credit card that can work on both sides maybe, but I think the interest rates would be ridiculous. On top of that, you would have pass the approval process.

Strangely enough I've had no problem using Paypal via my account. That being said, I haven't tried my Mastercard/debit but when I buy something from KS overseas and it won't charge I just ask them to accept it.
Apparently it's an anti-Fraud measure. Except for that my card is international and I live in the US so I don't see the problem.
Speaking of international cards, I wish JCB would get established nationwide in the US so I could get it. I mean that card is accepted EVERYWHERE in Japan so I would have no issue using it or an ATM there then.

I have to highly doubt the debit card problem. Have you been able to make purchases from oh, say Amazon Japan with your card? How about using that as payment method. What error pops up? If there's a problem, it's with the issuing BANK not the card. I am also betting you don't have a Visa/Mastercard debit card. I'm in the USA and I made a purchase using it. I prefer to use paypal as despite it being in USD, my bank adds 4%. Personal debit card? Don't use it as debit. Use as credit. It is a visa or mastercard, right?

Is your bank account not linked to Paypal? If you have the debit card linked only seems to make sense that you'd have the account too. Not trying to pry into your personal finances, but that would be the most logical thing.
Why would CD Projekt Red run a design contest for GOG? CD Projekt, sure. But CD Projekt Red?

On the topic of declined payments, your best bet is on factual information and talking directly with the respective parties without any middle men.

- Contact your card supplier directly and politely let them know what you're trying to do and whether or not you can do it. If not, see if they can recommend any other options you might be able to take.
- Contact paypal and/or any other payment processors you have accounts with or may be able to work with and do the same, explore all of your options directly to the horse's mouth.
- Contact GOG support finally to see what suggestions they may have to offer.

As an additional tip, GOG's own payment processing occurs in Cyprus, which for whatever reasons is on the radar of many banks and card companies as a hotbed for fraudulent activity. As such, in North America at least it is not uncommon for someone's first transaction to GOG to get rejected by their card/payment processor security division as a pre-emptive measure against potential fraud when they see "Cyprus" show up. If this is the case, you will need to contact your payment provider's security team and instruct them to permit payments to GOG.com through Cyprus, and they should be able to put a note on the file that such transactions are legitimate. This is what I had to do with MasterCard from Canada, after which everything was fine. Paypal or other payment processors may or may not require similar phone call to call off the security dogs.

On a secondary note about HOMM3, you can get HOMM3 for far less than $10 if you wait for it to show up in a GOG sale. I got the complete Heroes of MIght and Magic collection, the entire Might and Magic collection, the Heroes Chronicles collection and a bunch of other games here on GOG during a seasonal promo for $20 total for the whole lot. HOMM3 probably counted for about $1 worth of that. You can use the http://isthereanydeal.com website to search for the game in question, then click on "view history" to see a complete history of the price of the game across all game retailers over the last few years. From this you can predict when it might go on sale on GOG next, and even set up a notification to be alerted via email to the game going on sale (anywhere). There is also a Firefox browser extension (ITAD) that can import your game wishlist into isthereanydeal website to get notified of any games you have wishlisted going on sale.

Hope this helps.

Cyprus https://en.wikipedia.org/wiki/Cyprus

Yes, I get that wrong about 98% of the time. :)

Man it went on sale for the complete edition. Will trade any dota 2 items in steam inventory(have 5 weathers) and steam cards for the complete edition. Currently trying out Disciples 2, but so far seems very slow paced and not a lot of different units. Any ideas for a trade let me know please, really wan to get this while on sale and never got a chance to try HoMM games.

There's an active trading scene here, but if you want to get involved in that, there's two things you should know:
1. We have a big scammer issue here, so be VERY wary and get some tips from the locals on how to proceed if anything looks even remotely fishy.
2. You're gonna have a hard time trading Steam cards or DOTA items here. People avoid Steam like the plague, the trading card system even moreso, and it's rare you find folks here who play F2Ps, which they also tend to look down upon.

K thanks zeogold. Noted.