Is my heat sink calculation for the LM317 correct?
You're on the right track but there are two numbers you're missing: maximum junction temperature and the thermal resistance between the junction and case.  Going off of ST's datasheet, the maximum junction temperature is 125C and thermal resistance between the junction and case is 5 C/W.  I'd go with an ambient temperature of at least 30 (wouldn't want your circuit to burn up on a hot day) and put a reasonable buffer in for additional resistance between the case and heatsink (which you can reduce with thermal grease).  With a maximum junction temp of 115, ambient of 30, that means you need a heatsink with a natural convection resistance to ambient of 13.9 C/W or less.  There are plenty of heatsinks out there with that level of performance but some of the little dinky stamped aluminum ones are up around 30 C/W so make sure you check first.  Also: those numbers are assuming you're using a TO-220 package.