These are interesting, and I know you didn't make them up, you're simply citing these "paradoxes". However, I view them as fallible because they're sort of like scientific experiments: they need a very specific context in order to "function" (ie, stay paradoxical). If you apply just a little more contextual complexity to them, they simply become nuanced assertions... but no longer paradoxical.
1. The liar: under specific conditions, sure, it's paradoxical. (It's affirming itself false, and if you say "true" intending to agree, you've accidentally disagreed because something can't semantically be true and false at the same time). However, apply this to just about any real-life scenario (other than the abstraction proposed), and it loses its paradoxical quality: "I am lying about having cheated on my wife", says someone accused of cheating on his wife. In order to verify the truthfulness of the situation, you can't rely on semantics alone; Instead, you rely on the possible evidence, the witnesses, etc, before simply taking the man's words for granted regardless of any manipulation tactics he might be using for fun. So, basically, the liar's paradox can only exist outside real life, rendering it useless but fun.
2. Ship of Theseus: I actually have a humorous article about this :) But to comment on it with a more serious tone, I don't think it's fair to say any given object no longer belongs to its owner the moment its original constituting materials are no longer present due to decay/renovations. That's not simply because impermanence is inherent to life and you can't rely on absolute permanence alone in order to determine who owns what... But also, and most importantly, if this "paradox" was real, then we'd also have to change how we think about post-mortem gifts (such as the flowers you leave on a grave - surely they could be the same exact species the deceased person loved and used to keep at home, but it will never be THAT ONE, so... is it pointless to make offerings? If you believe in the Ship of Theseus Paradox, it's logical to say so). Or, a less morbid example perhaps, the human body itself: the tissues and cells that make up our bodies die and get renewed periodically. So...... is an adult no longer the same person as the baby they used to be? See the problem? This paradox is false, regardless of how famous was the person who proposed it.
3. The Barber Paradox is purely linguistic, interestingly enough. It only exists as far as you take the assertions literally and (like #1) devoid of any real-life application. Instead of a real Paradox (ie, an assertion that reveals a contradiction INHERENT to the phenomenon it's describing), it's an artificial one, because it assumes that people can't make inferences beyond what their verbal language is capable of describing, which begs the question: why assume languages should control us? We created languages. We control THEM. So much so, that we're constantly adding new words and meanings to the dictionary. It's not a "creature turning on the creator" scenario. The Barber [false] Paradox simply indicates an error in the wording of a piece of legislation, instead of anything materially verifiable. Even though the wording is poor, one can very easily understand that, yes, the barber shaves himself, because what matters in this law - the reason why it came to be in the first place - is its purpose, namely, to get men to shave; And not its purely semantic manifestation, namely, whether or not the term "shave themselves" has a double meaning. I bet any lawyer would agree.
4. The Omnipotence paradox: finally, a paradox that stands the test of practical application! No comments on this one. It is indeed paradoxical. :)
Anyway, this comment is just meant to start a fun conversation about where Western philosophy is going: is Semantics REALLY that much more important than Pragmatics? A lot of people here in the West seem to unconsciously think so, which explains why we're so easily fooled by the likes of cult leaders, radicalists, and other charlatans posing as "the ultimate saviour with the ultimate answer to [insert complex problem here]".
