The degree sign represents a nonbreaking space. Two words separated by such a space will always be on the same text line. Read more about nonprinting characters in Suzanne S. Barnhill's article at http://wordfaqs.ssbarnhill.com/NonprintChars.htm . (It is an http link which means that your browser may display a warning. However, the web site is safe, maintained by one of the Microsoft Word MVPs.)
Too many nonbreaking spaces in a document may cause a strange look, with text lines running short.
You can use Find & Replace (Ctrl+H in Word for Windows) and replace ^s with an ordinary space (just type in a space in the "Replace with" box).
EDIT: It seems you already tried the Find & Replace method. See my other reply for more suggestions.