I would have expected the Headings to use outline numbering but if you are having problems then try this variation
Code:
Sub ReplaceNumbers()
Dim oPara As Paragraph
Dim r As Range
For Each oPara In ActiveDocument.Paragraphs()
Set r = oPara.Range
If r.ListFormat.ListType = wdListSimpleNumbering And r.Style <> "Heading 1" Then
r.ListFormat.RemoveNumbers NumberType:=wdNumberParagraph
r.InsertBefore Text:="**"
End If
Set r = Nothing
Next
End Sub