Сам решил.
Если кому-то нужен ответ:
Imports Word = Microsoft.Office.Interop.Word
Dim WordApp As Word.Application = New Word.Application
Dim WordDoc As Word.Document
Public Function FindReplaceText(CellsValueWithLabel As String()()) As Boolean
'Find and replace texts from arrays
For Each cellsValue In CellsValueWithLabel
Try
If cellsValue(1).Length < 255 Then
If WordDoc.Content.Find.Execute(FindText:=cellsValue(0), ReplaceWith:=cellsValue(1), Replace:=Word.WdReplace.wdReplaceAll) Then
logHistory.insertLogHistory(Chr(34) + cellsValue(0) + Chr(34) + " - replaced by " + Chr(34) + cellsValue(1) + Chr(34))
End If
Else
Dim myRange = WordDoc.Content
While myRange.Find.Execute(FindText:=cellsValue(0))
If myRange.Find.Found Then
myRange.Select()
My.Computer.Clipboard.SetText(cellsValue(1))
WordApp.Selection.PasteAndFormat(Word.WdRecoveryType.wdPasteDefault)
logHistory.insertLogHistory(Chr(34) + cellsValue(0) + Chr(34) + " - replaced by " + Chr(34) + cellsValue(1) + Chr(34))
Clipboard.Clear()
End If
End While
End If
Catch ex As Exception
logHistory.insertLogHistory("********** ERROR ********** " + cellsValue(0) + " " + ex.Message.ToString())
End Try
Next
WordDoc.Save()
Return True
End Function