Many biological materials consist of sparse networks of disordered fibers, embedded in a soft elastic matrix. The interplay between rigid and soft elements in such composite networks leads to mechanical properties that can go far beyond the sum of those of the constituents. Here we present lattice-based simulations to unravel the microscopic origins of this mechanical synergy. We show that the competition between fiber stretching and bending and elastic deformations of the matrix gives rise to distinct mechanical regimes, with phase transitions between them that are characterized by critical behavior and diverging strain fluctuations and with different mechanisms leading to mechanical enhancement.