I've done it both ways. The diamond rods are not very coarse and I found that it removed steel slower than I would have liked. It's still much quicker than using the medium rods for the same purpose.
With sandpaper, I went to lowes and picked up some coarse and medium grit sandpaper. I then cut them into pieces slightly shorter than the sharpmaker rod and broad enough to wrap around all 3 sides. Then I wrapped it around the rod and taped around the top and bottom to keep it flat on the rod. Then I used the sharpmaker in the normal method. Since you're cutting into the paper, it doesn't last too long but the coarse grit takes metal off quickly. When the 2 edges are about to come together, switch to the finer grit. This will get the deep scratches out w/o wearing too much metal. Lastly, finish off with the ceramic rods.