Oh yes, you've certainly got that right. Interactions wil modify the propagator even in the case where you only have one photon. Remember that Feynman states that the propagator is basically a sum over all possible paths through which a photon can travel from A to B, with each path weighted by some weight factor (exp[i S] ).
For the interacting case there are many more ways in which a photon can travel from A to B. Now you also have to take into account -- as you correctly noted -- that a photon can temporarily turn into an particle/anti-particle pair, which afterwards annihilate again. But the photon can also do that twice, or three times, or in even more complex ways. All these different 'paths' that lead from A to B will contribute to the propagator. You will, however, quickly find that the more complex the intermediate process is, the smaller its contribution to the final propagator is.
For the case of two photons the same thing applies: photons can turn into particle/anti-particle pairs, and these pairs can then annihilate with each other (which is essentially how two photons can interact). You will find that the contribution of this intermediate process compared to the overal process is not that big at all -- which is not too suprising, because have you ever seen lightbeams collide?
Now, do keep in mind that you have to sum over all possible ways in which the photons can travel from A to B, so do not take these intermediate processes of particle creation too literal --- they are, in the end, nothing but a nice visualization way of interpreting the math. These intermediate states cannot be detected!