This works on your document:
Sub ChangeShadingAndThenDelete()
Application.ScreenUpdating = False
With ActiveDocument.Range
With .Find
.ClearFormatting
.Replacement.ClearFormatting
.Text = "*^13"
.Replacement.Text = ""
.ParagraphFormat.Shading.BackgroundPatternColor = RGB(0, 0, 0)
.Format = True
.Forward = True
.MatchWildcards = True
.Wrap = wdFindStop
.Execute
End With
Do While .Find.Found
If .Shading.BackgroundPatternColor = RGB(0, 0, 0) Then .Shading.BackgroundPatternColor = -587137025
.Collapse wdCollapseEnd
.Find.Execute
Loop
End With
With ActiveDocument.Range
With .Find
.ClearFormatting
.Replacement.ClearFormatting
.Text = "*^13"
.Replacement.Text = ""
.ParagraphFormat.Shading.BackgroundPatternColor = -587137025
.Format = True
.Forward = True
.MatchWildcards = True
.Wrap = wdFindStop
.Execute
End With
Do While .Find.Found
If .Shading.BackgroundPatternColor = -587137025 Then .Delete
.Collapse wdCollapseEnd
.Find.Execute
Loop
End With
Application.ScreenUpdating = True
End Sub