How to Find and Replace the Character ‘*’ in Excel

I would suggest the commercial product PowerGREP :

PowerGREP is a powerful Windows grep tool. Quickly search through large numbers of files on your PC or network, including text and binary files, compressed archives, MS Word documents, Excel spreadsheets, PDF files, OpenOffice files, etc. Find the information you want with powerful text patterns (regular expressions) specifying the form of what you want, instead of literal text. Search and replace with one or many regular expressions to comprehensively maintain web sites, source code, reports, etc. Extract statistics and knowledge from logs files and large data sets.

If you go the VBA route, try using Regular Expressions

Here's a start

Sub ReplaceWithRE()
    Dim re As Object 'RegExp
    Dim rng As Range, cl As Range
    Dim sh As Worksheet
    Dim wb As Workbook
    Dim sReplace As String
    Dim aReplace(0 To 1, 0 To 1) As String
    Dim i As Long

    Set wb = ActiveWorkbook
    Set re = CreateObject("vbscript.regexp") ' New RegExp
    re.Global = True
    re.IgnoreCase = False
    re.MultiLine = True

    ' Load array of patterns and replacements
    aReplace(0, 0) = "\bINT\b"
    aReplace(0, 1) = "INTERNATIONAL"
    aReplace(1, 0) = "\bNA\b"
    aReplace(1, 1) = "NATIONAL ASSEMBLY"

    For Each sh In wb.Worksheets
        On Error Resume Next
        Set rng = sh.UsedRange.SpecialCells(xlCellTypeConstants)
        If Err.Number <> 0 Then
            Err.Clear
        Else
            On Error GoTo 0
            For Each cl In rng
                sReplace = cl.Value
                ' Test each cell for each pattern, replace when found
                For i = 0 To UBound(aReplace, 1)
                    re.Pattern = aReplace(i, 0)
                    If re.Test(sReplace) Then
                        sReplace = re.Replace(sReplace, aReplace(i, 1))
                    End If
                Next
                cl.Value = sReplace
            Next
        End If
    Next


End Sub