Select/Highlight the row
Click Data-Text to columns
Select "Delimited" and click next
Check the box next to "space" and click next
Click Finish

This will move all of the " °C" to the next column so you can delete it.

I don't know why the find/replace method is not working for you.