We experimentally investigate the nonlinear transmission spectrum of coherent light fields propagating through a Rydberg-EIT medium with strong atomic interactions. In contrast to previous investigations, which have largely focused on resonant control fields, we explore here the full two-dimensional spectral response of the Rydberg gas. Our measurements confirm previously observed spectral features for a vanishing control-field detuning that are explainable by existing theories, but also reveal significant differences on two-photon resonance. In particular, we find qualitative deficiencies of mean-field models and rate-equation simulations in describing the nonlinear probe-field response under EIT conditions, suggesting spectral signatures of an interaction-induced resonance with laser-dressed entangled pair states. While this effect is captured by the third-order nonlinear susceptibility that accounts for pair-wise interaction effects, the experiments show that many-body processes beyond such two-body effects play a significant role already at surprisingly low probe-field intensities. These results suggest that a more complete understanding of Rydberg-EIT and emerging photon interactions requires to go beyond existing simplified models as well as few-photon theories.