In the case of the "bullet that pierces all vs. the armor that cannot be pierced" contradiction, I think some amount of scientific logic can be applied. In a situation where two equally powerful forces clash, the outcome is neutral. The bullet would not pierce the armor and the armor would not damage the bullet. This makes the statement that the bullet can pierce all and that the armor cannot be pierced false. However I don't think it's a true paradox.
As for what the fun is in paradoxes, it's that they make you think more deeply than the common riddle. While normal riddles make you think outside the box, paradoxes make you throw the box away and start looking under a bowl. It completely changes the game by making it an insolvable riddle that stretches the mind to its limits. Some people don't enjoy puzzles, but for puzzle people, there is no greater puzzle than the paradox.