What other definition of paradox is there?

Yeah, a literal contradiction. The purest example would be Russel's paradox: https://upload.wikimedia.org/math/b/e/0/be0bd5b59ed09618db93...

I like this variation:

"Both of these sentences are false. The sky is not blue."

It could be a literal contradiction, for example for someone religious, it may be paradoxical that evil exists given the existence of a benevolent all-powerful being, since that being either is unable to stop it or is choosing not to (which seems either not so all-powerful, or not so benevolent). Rather than change any of the beliefs that imply this paradox, believers can accept the beliefs and instead address the paradox through some other means, if at all.