Oh wait, it's not that bad...

XL help:
The settings for LookIn, LookAt, SearchOrder, and MatchByte are saved each time you use this method. If you don’t specify values for these arguments the next time you call the method, the saved values are used. Setting these arguments changes the settings in the Find dialog box, and changing the settings in the Find dialog box changes the saved values that are used if you omit the arguments. To avoid problems, set these arguments explicitly each time you use this method.
Revised code, includes setting to look in cell values, not formulae:

Sub AutoFormatRange()

Dim vStrings(0 To 3, 0 To 1) As Variant
Dim i As Integer
Dim rString As Range
Dim sFirstAddress As String

vStrings(0, 0) = "C"
vStrings(0, 1) = 3
vStrings(1, 0) = "Z"
vStrings(1, 1) = 4
vStrings(2, 0) = "V"
vStrings(2, 1) = 5
vStrings(3, 0) = "Maternity"
vStrings(3, 1) = 7


With Me
    .Range("FormatRange").Interior.ColorIndex = xlNone
    For i = LBound(vStrings) To UBound(vStrings)
        Set rString = .Range("FormatRange").Find(vStrings(i, 0), LookIn:=xlValues, lookat:=xlWhole)
        If Not rString Is Nothing Then
            sFirstAddress = rString.Address
            Do
                rString.Interior.ColorIndex = vStrings(i, 1)
            Set rString = .Range("FormatRange").FindNext(rString)
            Loop Until rString.Address = sFirstAddress
        End If
    Next i
End With
    
End Sub
Also includes revision to avoid unnecessary label, an improvement I achieved with no help from anyoen else.

Please try this.

CC