It will take me some effort to first clean up your rather muddled question before I can answer. I wouldn't have bothered except that one part of your question is very interestingly phrased. You said "leading a company towards innovation" rather than just "innovation." You are implying that innovation is a leadership problem rather than a business function. You are exactly correct, and a LOT of people miss that. Let me take your question apart piece by piece before answering.

The term 'paradigm shift' means something very precise in the philosophy of science. When an intellectual framework that covers the scope of a discipline slowly starts to show cracks and odd features/new discoveries that it cannot accommodate, and a new framework appears that explains all the old stuff AND the new/odd stuff, you have a paradigm shift. As a result, a lot of momentum shifts to new places, previously powerful people get sidelined, and people on the sideline suddenly occupy center-stage. Since all knowledge is interconnected in subtle ways, a paradigm shift causes a lot of change in every part of the world of knowledge.

Relativity is a basic example. It had effects as far away as literature and philosophy, besides turning physics upside down.

Using the term in this precise sense is extremely useful. Using it loosely as you have (and apparently, Gates), clouds things.

When this happens in technology, there is no set term. McLuhan used 'break boundary,' and I like that, but there are other terms. Heavier-than-air flight and silicon transistors are examples. The phenomenon has very different behavior in technology as opposed to science. See Mokyr's "Lever of Riches" to get a sense of it. Break boundaries fuel macroeconomic growth because they have an effect on the whole economy, not just their industry. Technology-innovation based growth is one of 3-4 types of growth distinguished by Mokyr (he calls it Schumpeterian growth, if I recall correctly... been a while since I read Mokyr).

When it happens on a much smaller scale that affects only a single market rather than the whole economy, you get an effect called "disruption." This is covered in detail in Clayton Christensen's work, who coined the term. Like paradigm shift, it is another term that is commonly misunderstood, with the consequence being needless confusion.

Now how does this relate to innovation? Disruptive innovation or break boundaries generally happen in the interstices of existing markets. So they are in everybody's "peripheral vision." Betting on disruption and break boundaries generally means creating new businesses, redrawing market boundaries, destroying old markets etc.

This is not the only kind of innovation. Christensen's work itself has one other type ("sustaining") and there's about a dozen other usefully well-defined types, worth distinguishing, which are analyzed in Geoffrey Moore's "Dealing with Darwin."

In general, existing well-managed companies explicitly set out to do every kind of innovation EXCEPT disruptive innovation. When they try, they usually fail. This was the subject of Christensen's research. Some companies are forced into trying disruptive innovation because they see a threat to their own markets. For example, ebooks threatening traditional books. Yet, when the threatened market players try to pre-empt and co-opt the disruptive force, they pretty much always fail. Typically, a different company does the disruption and kills or marginalizes the old one.

But companies persist in trying to do disruptive innovation. You can't blame them. They are fighting for their life.

Now to the interesting part of your question: what role does leadership play?

Consider A. G. Lafley's great definition of leadership: "interpreting external reality for the organization."

How a company innovates is strongly a function of leadership style because of this. If the leader has strong peripheral vision, and strong disruption anxiety, he/she will invest in disruption (or disruption hedging/insurance). This type of leadership takes a lot of courage because it always hits short-term performance to build a long-term strategic position. This is especially hard for companies under a lot of Wall Street pressure.

The other type of leader is staring straight ahead, with existing markets front-and-center, with very little peripheral vision. This type of leader responds to disruption threats by retreating deeper into its existing market by going upmarket, selling more value-added services to existing customers etc.

And of course, there's the third type of leader in the picture: the CEO of a disruptive startup (CEOs of non-disruptive startups are not leaders so much as outsourced middle managers for existing companies), for whom the disrupted market vision is front-and-center, even though it is on the periphery of the CEOs of the incumbent companies. This type of CEO is a "visionary" CEO because he/she is not in the A. G. Lafley business of interpreting external realities for the organization. S/he is in the business of communicating a future vision of a market that doesn't exist. When the market has been created, this type of visionary CEO often loses interest and steps aside for a Lafleyesque leader who can grow the new market and finish the job.

And (we're finally getting there!), the disruptor-CEO may either be leading a localized disruption effect, or participating in the generalized disruption enabled by a broader break boundary (i.e. "paradigm shift" in technology). The CEO riding a break-boundary (example, silicon 30 years ago, mobile today) can be either a Lafleyesque present-centric leader, if the break boundary has matured (i.e. the writing is on the wall), or the visionary type, when the evidence of a break boundary is very scattered.

So the short answer to your question is: "Yes, if the leader is the CEO of a disruptor startup that is taking advantage of a break-boundary."

That's only a tiny fraction of companies at any given time.