Well, you can do it in this pattern. You can add a counter and check it for every fifth occurence.
Dim myStoryRange As Microsoft.Office.Interop.Word.Range
For Each myStoryRange In doc.StoryRanges
With myStoryRange.Find
.Text = "targetstring"
.Replacement.Text = ""
.Wrap = Microsoft.Office.Interop.Word.WdFindWrap.wdFindAsk
.Execute(Replace:=Microsoft.Office.Interop.Word.WdReplace.wdReplaceOne)
End With
Next myStoryRange