Is having a piece of paper with 2 fake PINS a good solution to mitigate credit-card theft?

Anything you can do to mitigate the threat of usage after the physical-theft of the card is a great idea. Making them take longer by making them make mistakes and/or trying in multiple places is a solid idea. That is, aside from the ultimate mitigation of keeping your bank's phone numbers in your phone so you can contact them immediately to report card theft. As a piece of Social Engineering it's not the worst idea I've heard. Keeping that piece of paper in your wallet with the card might be a little more difficult and not worth the effort, but I could see it working.

In places where ATMs retain cards after several failed PIN attempts, this could be one extra level of security that might put less strain on your financial resources. Several card carriers also support larger PINs, up to 16-digits in some places. So you could enhance security on your card that way as well. You could also keep multiple closed credit cards in your wallet so it takes longer for the would-be thief to make an attempt on your good cards.

That being said, I don't know how often you expect to have your card stolen, and taking steps to prevent its theft in the first place might be more effective than a Social Engineering attempt at mitigation. Locking your wallet in a drawer at night, keeping it in your front pocket or carrying it in an odd location on your body (sock, inside your button-up shirt, secure pocket with a zipper) might be better techniques to avoid the theft in the first place.