IMHO the best way to do it is to count the worst case. Take minimum output voltage, maximum input voltage, subtract those two (you'll get maximum voltage on LM317), multiply that by maximum output current and you will get the power that you need to dissipate.
For few Watts, it's usualy better to use small heatsink without thermal pad (mind that it's gonna be connected to output pin as mentioned before). You can even screw that heat sink to the board in the place where the output route is.
I would personally use thermal pad and spacer only if it's necessary (f.e. for more than one device on the same heatsink, when you use the back of the case as heatsink or if the output voltage gets too high), as it always adds some thermal resistance.