We report measurements of the nonlinear conductance of InAs nanowire quantum dots coupled to superconducting leads. We observe a clear alternation between odd and even occupation of the dot, with sub-gap-peaks at $|V_{sd}|=Delta/e$ markedly stronger(weaker) than the quasiparticle tunneling peaks at $|V_{sd}|=2Delta/e$ for odd(even) occupation. We attribute the enhanced $Delta$-peak to an interplay between Kondo-correlations and Andreev tunneling in dots with an odd number of spins, and substantiate this interpretation by a poor mans scaling analysis.