More efficient alternative to Find-Replace Loop?

I was tasked with looking through a 10,000 row by 20 column spreadsheet for 628 different ID Codes and replacing them with their Descriptions. The ID Codes could appear individually in any of these cells (200,000 cells!).

The list of ID's and Descriptions hardly ever changes, so I decided to create the two-dimensional array as part of the find-replace macro shown below (only a few lines of each dimension are shown).

My question isn't related to that (although if you can suggest a better alternative please do). The main "work" of the macro is the loop at the end of the array declarations, which essentially loops through all 628 ID codes in array dimension 1 and does a Find-ReplaceAll with its corresponding Description from array dimesion 2.

This task, manually, could take days. My macro has whittled the task down to 2.5 minutes on a 5-year-old laptop, but I was hoping one of the gurus might suggest an even better method than 628 loop iterations. If not, so be it, the end users will appreciate what I've done and then have to find something to do with their "free time."

Option Base 1
Option Explicit

Sub ReplaceStuff()
Dim i As Long
Dim arr(2, 628) As Variant
Application.ScreenUpdating = False
arr(1, 1) = "19142"
arr(1, 2) = "19144"
arr(1, 3) = "19146"
.
.
arr(1, 626) = "E97"
arr(1, 627) = "E98"
arr(1, 628) = "E99"
arr(2, 1) = "Company A"
arr(2, 2) = "Company B"
arr(2, 3) = "Region M"
.
.
arr(2, 626) = "Country A"
arr(2, 627) = "Company 42"
arr(2, 628) = "Country T"

For i = 1 To 628
Cells.Replace What:=arr(1, i), Replacement:=arr(2, i), LookAt:=xlWhole, _
    SearchOrder:=xlByRows, MatchCase:=False, SearchFormat:=False, _
    ReplaceFormat:=False
Next i
Application.ScreenUpdating = True
End Sub

Happy Excelling!