I believe that the clearformatting is necessary although that doesn't appear to be the case in this instance. Before running the macro, use the regular find/replace dialog to find something formatted a particular way such as Bold or a style perhaps. If you close that dialog and then re-open it, you will see that it remembered this in your previous find. If you then run your macro without clearing those settings the macro has the potential to include those settings in its search. This is why it is good practice to clear this.
However, now that I am testing it, the code seems to ignore those settings which surprises me. In the case of your code, I would have said that you could remove the two lines in the middle
End With
With Selection.Range.Find
since they are not strictly needed but if you do, the strikethrough is ALSO a factor in the second search.
Since you are removing underlining, I would shorten the code and ensure you remove all types of underlining regardless of type. There is no need to search to remove underlining whilst retaining the text
Code:
With Selection.Range.Find ' Get rid of any stricken-through text
.ClearFormatting 'Is this needed?
.Replacement.ClearFormatting 'Is this needed?
.Text = "*"
.MatchWildcards = True
.Font.StrikeThrough = True
.Replacement.Text = ""
.Execute Replace:=wdReplaceAll
End With
Selection.Range.Font.Underline = wdUnderlineNone 'remove all underlining regardless of type