Вызовите вашу процедуру в петле :
Sub ProcessAllSheets()
Dim s As Worksheet
For Each s In Sheets
Call changeLinks(s.Name)
Next s
End Sub
С этими изменениями в вашей программе:
Sub changeLinks(s As String)
Const oldPrefix = "\\oldServer\common"
Const newPrefix = "\\NewServer\common"
Dim h As Hyperlink, oldLink As String, newLink As String
For Each h In Sheets(s).Hyperlinks
'this will change Address but not TextToDisplay
oldLink = h.Address
Debug.Print "Found link: " & oldLink
If Left(oldLink, Len(oldPrefix)) = oldPrefix Then
newLink = newPrefix & Right(h.Address, Len(h.Address) - Len(oldPrefix))
h.Address = newLink
Debug.Print " Changed to " & h.Address
End If
Next h
End Sub