We studied the low-energy states of spin-1/2 quantum dots defined in InAs/InP nanowires and coupled to aluminium superconducting leads. By varying the superconducting gap, Δ, with a magnetic field, B, we investigated the transition from strong coupling, Δ > T_{K}, where T_{K} is the Kondo temperature. Below the critical field, we observe a persisting zero-bias Kondo resonance that vanishes only for low B or higher temperatures, leaving the room to more robust sub-gap structures at bias voltages between Δ and 2Δ. For strong and approximately symmetric tunnel couplings, a Josephson supercurrent is observed in addition to the Kondo peak. We ascribe the coexistence of a Kondo resonance and a superconducting gap to a significant density of intra-gap quasiparticle states, and the finite-bias sub-gap structures to tunneling through Shiba states. Our results, supported by numerical calculations, own relevance also in relation to tunnel-spectroscopy experiments aiming at the observation of Majorana fermions in hybrid nanostructures. ; Comment: 11 pages, 7 figures