The OP already mentioned 1 technique to resolve a paradox: reject a premise, a definition, identify a fallacy, etc. Another solution is a paradigm shift. I think perhaps looking at a historical example or two may help.
1) Russell's Paradox (aka Russell-Zermelo paradox)
Russell found a fundamental error in Frege's system of logic, which included naive set theory, and which he famously rephrased as a puzzle: There is a small town where the barber shaves those men, and only those men, who do not shave themselves. Does the barber shave himself? If you answer 'yes' then the barber can't shave himself, If you answer 'no' then the barber must shave himself.
This puzzle reveals a paradox in naive set theory: can the set of sets that are not members of themselves, be a member of itself? If you answer yes, it can't be a member of itself. If you answer 'no' then it must be.
There was no simple solution to this problem and indeed several solutions were developed to address it. One is to scrap the Comprehension Axiom and replace it with the Separation Axiom. That may not sound like a paradigm shift, but consider what happens when you add or remove axioms from Euclidean geometry.
There are other solutions- axiomatic set theories, natural set theories; Classes , Types, etc. But most new set theories required a shift in our understanding of what mathematics is, and thus constitute a paradigm shift within mathematics.
2) Achilles and the Tortoise
One of Zeno's paradoxes against motion involves Achilles chasing (or racing) a tortoise. The tortoise is a head of Achilles. For him to overtake it, he must first travel half the distance. And then half the distance again. And then half of the remaining distance, etc. The idea is that you can always divide the given distance in half, so in theory there is an infinite amount of distance to cover.
Clearly, Achilles can catch the tortoise, but how do you explain it? The problem seems to be with the ability to divide a distance ad infinitum. Ancient philosophers spent a considerable amount of time trying to solve this problem, including Aristotle who admitted that his proposed solutions were not convincing.
This paradox can be solved by considering the distance between Achilles and the tortoise as the sum of an infinite series, which in turn presupposes the concept of infinity. Since Calculus students learn this in high school this doesn't appear to be a big deal today, but infinity was controversial even when Leibniz (and Newton) invented Calculus, more than a thousand years after Zeno formulated his paradoxes. The point is that this required a new branch of mathematics to solve, and thus it required a paradigm shift.
There are numerous paradoxes in the history of philosophy, mathematics, and science. These examples certainly don't cover all of them, but hopefully they show how a paradigm shift can help resolve problems that were previously insurmountable.