Fragile Logic
I hate to announce this, but "violating logic" is the easiest thing in the world. Anyone can do it! Here, I'll show you:
Given:
A -> B
B -> C
Therefore:
C -> A
In fact, it does not logically follow that C implies A from the givens. I just "violated logic". I guarantee you with my life that I have no super-powers and am not omnipotent. But perhaps that is unsatisfying, because I didn't levitate a rock or cause a dog to age backwards into a puppy. Well, it turns out that those things have only a tenuous connection to logic. We can only associate real-world events with logic by fiat. There is no "intrinsic" or "absolute" logical system attached to reality. We can't scrape away the paint of reality and peer at the "Logic System v3" etched into every physical thing. There is no such label.
Many Logics
As mentioned by others, there are many competing logical systems. You have Aristotelian Logic, Intuitionistic Logic, Fuzzy Logic, etc ad nauseum. None of these can claim to be "The One True Logic(TM)" because the very concept does not make sense. Logics are formal systems. They are a set of rules and statements. The rules tell you how the statements can be combined or modified to produce other statements. Some formal systems are used to describe what happens in the physical world, but this description is merely correlative, not determinative. We can say: "We observe the hydrogen atom to obey the Bohr model", but we cannot say: "The Bohr model causes the hydrogen atom's behavior", because it quite clearly does not.
The reason formal systems must define a set of rules is because what makes systems different is exactly which rules they adopt (the axioms and rules of procedure). And the fact that there are many different rule choices one can define leads to the existence of an infinite number of formal systems. So when someone says: "That defies logic!" the first response should be: "Which one?" The second response should be: "That's ok, it's perfectly consistent with Logical System {X}."
Omnipotence
Next, we should ask: "What is omnipotence?" And to answer that, we should back up and ask: "What is potence?" I mean, what does it mean to have power at all? And I think we generally agree that it means the ability to cause some state change in the universe. If the universe just stays in the same state for all eternity, most folks won't say: "It's doing that because of my infinite power." But if a small rock goes flying through the air, someone might say: "I threw the rock. It's going fast because I have great power." And we understand what that means. If a boulder the size of a house goes flying through the air, and someone says: "I caused that boulder to fly", then we are awed by the display of power. We recognize that causing that sequence of state changes in the universe is non-trivial and won't just happen spontaneously under most circumstances.
However, we also recognize that the bigger the difference between State A and State B when B follows A is some kind of measure of the "power" of something (whether an inanimate force or an intelligent agent). Thus, we can enumerate the set of possible state changes under a small, finite power (say, a robot with 1 W of power available to it). This set of universe-histories defines the scope of the power of that entity. As the power increases, the space of possible universe-histories expands. And thus, we can see that a being with unlimited power would simply have the ability to cause any universe-state to follow any other universe-state. It could cause a universe with a billion stars to immediately be followed by a universe with 0 stars and 5 unicorns. Now, lots of folks will step in and say: "But that's illogical! Impossible!!!" And if you subscribe to the Standard Model, that is all true. But if you recognize that the Standard Model just describes what we see, and not what an omnipotent being is capable of, then such a transition is not really "illogical" at all. We just haven't witnessed it yet (and I'm sure most of us are hoping not to).
But viewing power as the ability to choose the future histories of the universe sheds light on the old conundrum of "making a rock so big you can't lift it". The very idea of an "unliftable rock" is not really a demonstration of power under this description. Because sufficient power will always allow any object to suddenly translate to any location at all. The ability to "create" an "immovable object" really boils down to the ability to prevent any future history in which that object changes its position. But for an omnipotent being that can select any next state from the set of all possible states, such a future history is merely contingent upon their will. If that rock never moves, it is only because the omnipotent being wills it so, despite the actions of all finite beings. And so, relative to itself, the rock is moveable. But relative to everyone else, it is not! Such an omnipotent being is self-consistent from this perspective.
Uniqueness
We immediately see a problem if one suggest that there are two omnipotent beings. Because if both beings are truly omnipotent, then each one may select any future universe-state which pleases them. So what happens if they select different universe-states? If there's only one universe, then you have a bona-fide logical contradiction. We can't even describe a universe that is in two states simultaneously (unless you subscribe to the Many-Worlds interpretation of QM). So, omnipotence as I've described it can be possessed by at most one willful entity.
Benevolence
What is impossible is for a being to be "omnibenevolent". Imagine that there are three people: Adam, Eve, and Lilith. Both Eve and Lilith desire Adam for themselves, and to the exclusion of the other (they don't like to share). Eve considers a "benevolent God" to be one that causes her to acquire Adam, while Lilith believes the same for herself. Clearly, God cannot satisfy both wishes simultaneously, because even if he clones Adam, the exclusivity is then violated (these are jealous women who obtain satisfaction from having Adam to themselves). The problem is not that God is unable to choose the winning universe-state which solves the conflict. The problem is that the "benevolent states" are ill-defined.
The concept of "benevolence" boils down to value judgments. And there is nothing more contentious amongst humans than their values. We don't know what an omni-benevolent being would look like, because we wouldn't even recognize omnibenevolence if it were happening right now! "Benevolence" implies some kind of "goodness", but most humans define "goodness" in a fairly self-centered way (such as: "Me being alive is good"). Multiple humans define it in ways which are mutually exclusive practically every single day of their lives. For a simple example, try to get 10 random people to agree whether a serial killer who has repented deserves to go to heaven or not. Even if it were possible for an omni-benevolent being to exist, a large number of humans would curse it out for any choice it made on this question.
Free Will
If we want to make impossibility statements about super-powered beings, it seems most fruitful to ask the question: "What is free will in the presence of omnipotence?" My answer is: "It doesn't look like anything. There's nothing there." (Or, if you prefer: "It looks like John Cena") After all, if some action occurs because a mere human "willed it", we know that the omnipotent being really chose that universe-state, either actively (by "pushing a button"), or passively (by allowing "the program" to execute). It's possible that the omnipotent being creates "holes" in their own power to give space for freely-acting agents, but the problem with this scenario is that it is exactly indistinguishable from one in which the omnipotent being merely caused the sequence of events by fiat (including the feeling of having exercised free will!). So it doesn't really matter if these "power holes" exist or not, because the only one who can tell the difference is the omnipotent being (and from what I can tell, the difference doesn't actually mean anything to such a being anyway).
This is a fancy way of saying that we are free (even entitled) to blame everything in history on the omnipotent being. They literally have no defense. This is one of the true limitations of being omnipotent. Even if they claim to "give up" a part of their power, there is literally no test they can offer us to convince us that has actually happened. It's really just a charade, and an embarrassing one, at that. It's not really embarrassing for us so much as for the Being, who is trying to trick his own creation into thinking something that he can just cause to happen by his will anyway. So in a roundabout way, the omnipotence is kinda trying to fool itself. I think this is the real problem with omnipotence. And if it sounds like an alternative telling of the Problem of Evil, that's because it is.