When mine are babies I do paper train them within the kitchen - then gradually reduce the amount of paper until just one section remaining. Then comes the interesting part - when they head for that paper - I know they need to go out. I also have a 'paper' by the door we use to go out to the dog yard - so head for paper - go outside - pretty quickly don't need paper at all as they go to the door.
With adult dogs who know the 'door' I find that the puppies just follow and the previous generation teaches the new generation.
(guess they only need me to bring the food)
and they don't tear the paper? Geez, mine LOVE LOVE LOVE to shred paper. No paper on the floor is safe. I am amazed that yours leave it alone and actually use it properly!