I would strongly recommend using INDEX/MATCH, rather than a VLOOKUP. It is much quicker when dealing with a large number of formulas. Also, although your requirements are very basic, INDEX/MATCH is much more versatile, so would be useful in more complex situations.

=IFNA(
    INDEX(3:10,MATCH(DD$10,0)),
    "Not Found"
)

EDIT: I miss understood what the OP wanted...

Sorry. I think what you actually want is the original data to be overwritten. So the cell containing "Jersey", changes to contain "Zone 1" instead. I don't think this is possible without a VBA macro.

You could create a separate sheet which would act as a read only report. It would be identical to the original "input" sheet, except that it changes the cells containing countries to zones.

Here is a macro and instructions:

Sub FixFormulas()
    Dim r As Range, rng As Range
    Dim s As String

    Set rng = Cells.SpecialCells(xlCellTypeFormulas)
    For Each r In rng
        r.Value = "'" & r.Formula
        r.Replace what:="2015", Replacement:="2016"
        r.Replace what:="Data15", Replacement:="Data16"
        r.Formula = r.Value
    Next r

End Sub

Macros are very easy to install and use:

1. ALT-F11 brings up the VBE window
2. ALT-I ALT-M opens a fresh module
3. paste the stuff in and close the VBE window

If you save the workbook, the macro will be saved with it. If you are using a version of Excel later then 2003, you must save the file as .xlsm rather than .xlsx

To remove the macro:

1. bring up the VBE window as above
2. clear the code out
3. close the VBE window

To use the macro from the Excel worksheet:

1. ALT-F8
2. Select the macro
3. Touch RUN

To learn more about macros in general, see:

http://www.mvps.org/dmcritchie/excel/getstarted.htm

and

http://msdn.microsoft.com/en-us/library/ee814735(v=office.14).aspx

Macros must be enabled for this to work!

EDIT#1:

Discard the previous code and use this instead:

Sub FixFormulas2()
    Dim r As Range, rng As Range
    Dim s As String

    Set rng = Cells.SpecialCells(xlCellTypeFormulas)
    Set rng = Intersect(rng, Range("Z4:AA120"))
    For Each r In rng
        r.Value = "'" & r.Formula
        r.Replace what:="2015", Replacement:="2016"
        r.Replace what:="Data15", Replacement:="Data16"
        r.Formula = r.Value
    Next r

End Sub

(we are only adding a single line of code)

Excel Multi Replace

1. Open your VBA editor (Alt+F11) and paste the below macro anywhere
2. Set up a two-column lookup range: 1st column is the value to search for, 2nd the value to replace
3. Select your input range where values should be replaced like shown in the 1st picture
4. Execute the macro (Alt+F8).

The macro asks where your Lookup range is. First the sheet name, then the Lookup range address. Enter only the first column e.g A1:A2 for the example below.

That's it. Now the macro begins to iterate through all replace rules and applies them like a
normal Excel Search & Replace (Ctrl+H) onto your selected input range.

Input range            Replace rules               Input range after macro

Sub MultiReplace()
On Error GoTo errorcatch
Dim arrRules() As Variant

    strSheet = InputBox("Enter sheet name where your replace rules are", _
        "Sheet name", "Sheet1")
    strRules = InputBox("Enter address of replaces rules." & vbNewLine & _
        "But only the first column!", "Address", "A1:A100")

    Set rngCol1 = Sheets(strSheet).Range(strRules)
    Set rngCol2 = rngCol1.Offset(0, 1)
    arrRules = Application.Union(rngCol1, rngCol2)

    For i = 1 To UBound(arrRules)
        Selection.Replace What:=arrRules(i, 1), Replacement:=arrRules(i, 2), _
            LookAt:=xlWhole, MatchCase:=True
    Next i

errorcatch:
End Sub