Art's fix is a good one (I use it all the time in paragraphs that include superscripts or subscripts), but I haven't been observing any spacing issues to begin with when I insert the degree symbol. Maybe it's dependent on typeface (we use Times New Roman for body text in my shop), but maybe not: Are you using a proper degree symbol, or are you superscripting a lowercase o (a common trick among authors whose work I edit)?
FWIW, you can insert the degree symbol by typing
i <control>-q <shift>-1.