The Omnipotence Paradox is a type of argument that attempts to show that omnipotence is inherently contradictory, and that an omnipotent God could not exist. While not all Deists believe in an omnipotent God, many Classical Deists do which makes it important to see how the paradox can be resolved or refuted.
Omnipotence refers to the ability to do anything. Humans are finite beings and cannot do things beyond their limits. For example, I cannot levitate or go flying by myself even if I wished to. Therefore, the power of human beings is finite. However, an omnipotent being does not have finite power. An omnipotent being is not constrained and could go flying or levitate or do everything we cannot. God (or gods) were not always viewed as omnipotent especially prior to Christianity, however omnipotent conceptions of God have become popular due to how they fit into certain philosophical stances. Any Deist view of God as a necessary being almost certainly requires an omnipotent God, as a finite God could be contingent and thus not be a necessary being.
Various omnipotence paradoxes cast doubt on the possibility of an omnipotent being by asserting that such a being would lead to logical contradictions. One of the most famous paradoxes is "Could God create a rock that he could not lift?". If God could create such a rock, he would not be omnipotent since he would be unable to lift the rock. If God could lift the rock, he would be unable to create a rock that satisfies the condition of the paradox and would not be omnipotent. There are many similar versions to this. Another example is whether God could create both an immovable object and an unstoppable force.
I won't dispute that these can't be done, but that doesn't mean I accept the conclusion that an omnipotent being can't exist. In fact, for the paradox to hold, we have to presuppose something that allows us to view omnipotence in a new light. God cannot create a rock he cannot lift because it is logically contradictory. Events or occurrences that are logically contradictory cannot happen. Logic is the necessary structure of reality. Therefore, if we define omnipotence to be the ability to do anything logically possible then the omnipotence paradoxes do not disprove an omnipotent being.
I expect some to argue that such a definition is arbitrary, however it is perfectly coherent when considering that logic is the inherent structure of reality. If non-logical propositions cannot be actualized then "the ability do anything" is equal to "the ability to do anything logically possible" because non-logical propositions are effectively "non-things". Therefore, the inability to create a rock that God cannot lift is an inability to do a non-thing. This does not go against the postulate of an omnipotent being. It does go against certain concepts of Theist God(s) that can do logically contradictory things, but this gets into murky territory. If true, a universe could both exist and not exist at the same time, or a God could exist and not exist at the same time. I would encourage Deists to avoid this view.
In conclusion, the consistent application of the laws of logic means that an omnipotent God could still exist. In my view, this is necessarily the case although this article itself does not touch upon arguments for God, only that the omnipotence paradoxes do not disprove what they claim to. It is also important to keep close notice of the relationship between God and logic. Logic cannot precede God, because that would mean God isn't a necessary first cause. However, God cannot precede logic because this implies that a non-logical universe could exist. There are limits to what we can speculate, but the view that logic is an inherent component of God seems right to me (although I would not encourage arguments for "parts/wholes" of what God is).