Using Excel 2000, I've done this by saving an "AutoCorrect" entry in Microsoft Word (yep...Word), which is then accessed by Excel to make it the way I want it. In Word, I inserted the degree symbol followed by upper case C, then highlighted it, selected Tools, AutoCorrect, then entered "degc" in the "Replace" text box. Click OK, be sure to save Normal.dot when you exit Word. You may have to re-open Excel for it to recognize the new auto-correct entry. Once you do that, if the chart already has an axis that you want to label with oC, just edit the axis label, entering degc followed by a space, and you'll have your oC. If it doesn't already have an axis label, add one using chart options (the auto-correct won't work in the dialog box), then edit it as above.
Hope this helps,
Cindy
Edit...I just re-read your post, and this won't really do what you want...you want the degree symbol on the number, not just on the axis label, and as-described, it would give you degrees C, not just the degrees symbol (although it could be changed to do that). Hope you find a working solution.