See http://word.mvps.org/FAQs/MacrosVBA/ModifyRecordedMacro.htm.

This sort of information is beyond the capabilities of the macro recorder -
the following should do what you want:
http://www.gmayor.com/installing_macro.htm

Sub ReplaceStyle()
Dim FindStyle As String
Dim ReplaceStyle As String

FindInput:
FindStyle = InputBox("Enter name of STYLE to change", _
"Find Style")

ReplaceInput:
ReplaceStyle = InputBox("Replace " & _
FindStyle & " with which STYLE?", _
"Replacement Style")

   Selection.HomeKey Unit:=wdStory
   Selection.Find.ClearFormatting
   On Error GoTo FindError
   Selection.Find.Style = ActiveDocument.Styles(FindStyle)
   Selection.Find.Replacement.ClearFormatting
   On Error GoTo ReplaceError
   Selection.Find.Replacement.Style = _
   ActiveDocument.Styles(ReplaceStyle)
   With Selection.Find
       .Text = ""
       .Replacement.Text = ""
       .Forward = True
       .Wrap = wdFindContinue
       .Format = True
       .MatchCase = False
       .MatchWholeWord = False
       .MatchWildcards = False
       .MatchSoundsLike = False
       .MatchAllWordForms = False
   End With
   Selection.Find.Execute replace:=wdReplaceAll

   Selection.Find.ClearFormatting
   Selection.Find.Style = ActiveDocument.Styles(ReplaceStyle)
   Selection.Find.Replacement.ClearFormatting
   Selection.Find.Replacement.Style = _
   ActiveDocument.Styles("Default Paragraph Font")
   With Selection.Find
       .Text = ""
       .Replacement.Text = ""
   End With
   Selection.Find.Execute replace:=wdReplaceAll

   End
FindError:
   MsgBox Prompt:=FindStyle & " Style does not exist", _
       Buttons:=vbExclamation, _
       Title:="Error!"
   GoTo FindInput
ReplaceError:
   MsgBox Prompt:=ReplaceStyle & " Style does not exist", _
       Buttons:=vbExclamation, _
       Title:="Error!"
   GoTo ReplaceInput

End Sub