Why must both the critical temperature and pressure be exceeded to achieve the supercritical phase?
The critical point is a phase transition of phase transitions.  It's a different beast than your everyday run-of-the-mill phase transition like water boiling to vapor or ice melting to water.

The diagram you included is very misleading in its use of color.  The "yellow" supercritical regime doesn't really exist.  Beyond the critical point, gas is indistinguishable from liquid.  So instead of having a special yellow region, the supercritical region should be some gradient of green (liquid) and pink/orange (gas).  The vapor pressure curve between the triple point and critical point is the curve along which liquid is in equilibrium with gas, i.e. those phases have the same molar free energy $G$.  However, they obviously differ in many other properties, including molar enthalpy $H$, molar entropy $S$, molar volume $V$, etc.  Moving along a trajectory in $PT$ space that crosses the vapor pressure curve results in a discontinuity of those values.  Thus, such a phase transition is a first-order phase transition, as first-order derivatives of $G$ (such as $S=\left (\frac{\partial G}{\partial T}\right )_{P}$ and $V=\left (\frac{\partial G}{\partial P}\right )_{T}$) are discontinuous through the transition.

As you move along the vapor pressure curve closer to the critical point, the size of the discontinuous jump in $S$, $H$, $V$, etc. gets smaller and smaller.  Finally, at the critical point, the discontinuity disappears.  So the existence of a first-order phase transition goes away, and no phase transition at all takes its place.

Say you were to start with liquid $\ce{CO2}$ at a $T$ slightly below and $P$ slightly above the critical point, and move through $PT$ space in a counterclockwise cyclic orbit around the critical point.  As you lowered $P$, there would be a distinct first-order phase transition to gas -- the $\ce{CO2}$ would boil -- but then as you reached the bottom of the circle and started increasing $P$ and $T$, moving past the critical point, there would be no phase transition at all as you went to the yellow region in your chart.  There would similarly be no phase transition as you reached the top of the circle and moved back into "green" territory.  You'd get liquid carbon dioxide again, and when you go again through the circular path through $PT$ space, it would boil -- a distinct first-order phase transition -- again.  But it would never condense, in the sense of a sudden change from gas to liquid.  The change back to liquid $\ce{CO2}$ would be gradual, with no discontinuities.

So to specifically answer your questions:


  what is the physical explanation for why it's necessary for both the critical temperature and critical pressure both to be exceeded simultaneously in order for this phase transformation to occur?


The pseudo-fallacy in the question is using the phrase "phase transformation" to describe critical phenomena.  Passing the critical point is not a first-order phase transition like boiling water under normal conditions.  It's a much higher-order phase transition.  Here's a good chapter with more info.


  The fact that increasing pressure on a supercritical fluid can eventually drive it to a solid phase would seem to imply that it's not quite that simple. See, for example, the phase diagram of carbon dioxide.


Think in terms of free energy landscapes.  Solid, liquid, and gas phases are at the bottom of potential wells or pits in this $G$ surface.  Past the critical point, the liquid "well" and the gas "well" are no longer distinct minima, but are the same.  However that doesn't change the fact that if you move "up" in the free energy landscape by increasing $P$, you will eventually find the still-distinct pit (free energy minimum) for solid.