Do I need an array, class, dictionary, or collection?

Class Module is the answer. It's always the answer. Code is code and there's almost nothing you can do in a class module that you can't do in a standard module. Classes are just a way to organize your code differently.

But the next question becomes how to store your data inside your class module. I use Collections out of habit, but Collection or Scripting.Dictionary are your best choices.

I'd make a class called CCountry that looks like this

Private mlCountryID As Long
Private msCode As String
Private msFullname As String
Private msAbbreviation As String

Public Property Let CountryID(ByVal lCountryID As Long): mlCountryID = lCountryID: End Property
Public Property Get CountryID() As Long: CountryID = mlCountryID: End Property
Public Property Let Code(ByVal sCode As String): msCode = sCode: End Property
Public Property Get Code() As String: Code = msCode: End Property
Public Property Let Fullname(ByVal sFullname As String): msFullname = sFullname: End Property
Public Property Get Fullname() As String: Fullname = msFullname: End Property
Public Property Let Abbreviation(ByVal sAbbreviation As String): msAbbreviation = sAbbreviation: End Property
Public Property Get Abbreviation() As String: Abbreviation = msAbbreviation: End Property

Then I'd make a class called CCountries to hold all of my CCountry instances

Private mcolCountries As Collection

Private Sub Class_Initialize()
    Set mcolCountries = New Collection
End Sub

Private Sub Class_Terminate()
    Set mcolCountries = Nothing
End Sub

Public Property Get NewEnum() As IUnknown
    Set NewEnum = mcolCountries.[_NewEnum]
End Property

Public Sub Add(clsCountry As CCountry)
    If clsCountry.CountryID = 0 Then
        clsCountry.CountryID = Me.Count + 1
    End If

    mcolCountries.Add clsCountry, CStr(clsCountry.CountryID)
End Sub

Public Property Get Country(vItem As Variant) As CCountry
    Set Country = mcolCountries.Item(vItem)
End Property

Public Property Get Count() As Long
    Count = mcolCountries.Count
End Property

You see that CCountries is merely a Collection at this point. You can read more about that NewEnum property at http://dailydoseofexcel.com/archives/2010/07/09/creating-a-parent-class/

Then I'd put all my country stuff in a Table and read that table into my class. In CCountries

Public Sub FillFromRange(rRng As Range)

    Dim vaValues As Variant
    Dim i As Long
    Dim clsCountry As CCountry

    vaValues = rRng.Value

    For i = LBound(vaValues, 1) To UBound(vaValues, 1)
        Set clsCountry = New CCountry
        With clsCountry
            .Code = vaValues(i, 1)
            .Fullname = vaValues(i, 2)
            .Abbreviation = vaValues(i, 3)
        End With
        Me.Add clsCountry
    Next i

End Sub

I'd need a way to find a country by one of its properties

Public Property Get CountryBy(ByVal sProperty As String, ByVal vValue As Variant) As CCountry

    Dim clsReturn As CCountry
    Dim clsCountry As CCountry

    For Each clsCountry In Me
        If CallByName(clsCountry, sProperty, VbGet) = vValue Then
            Set clsReturn = clsCountry
            Exit For
        End If
    Next clsCountry

    Set CountryBy = clsReturn

End Property

Then I'd run down my list of numbers and put the codes next to them

Sub FillCodes()

    Dim clsCountries As CCountries
    Dim rCell As Range
    Dim clsCountry As CCountry

    Set clsCountries = New CCountries
    clsCountries.FillFromRange Sheet1.ListObjects("tblCountries").DataBodyRange

    For Each rCell In Sheet2.Range("A3:A5").Cells
        Set clsCountry = Nothing
        Set clsCountry = clsCountries.CountryBy("Code", CStr(rCell.Value))

        If Not clsCountry Is Nothing Then
            rCell.Offset(0, 1).Value = clsCountry.Fullname
            rCell.Offset(0, 2).Value = clsCountry.Abbreviation
        End If
    Next rCell

End Sub

Other than defining where the codes I'm looping through are, I don't really need any comments. You can tell what's going on my the name of the object and the properties or methods. That's the payoff for the extra work in setting up class modules - IMO.