Superconductivity in the two-dimensional Kondo lattice model is derived by means of the dual-fermion approach. This framework takes full account of local correlations based on the dynamical mean-field theory and further includes influence of critical antiferromagnetic fluctuations. It is found that pairing with dx2 -y2 symmetry similar to the Hubbard model appears only in the weak-coupling regime. As the coupling is increased, we observe transition to p-wave spin-singlet superconductivity. The emergence of the unconventional p-wave pairing is ascribed to formation of large Fermi surface, which embodies itinerancy of f electrons.