VBAで下記こ処理を行いたいと思っています。

Sub 変換()
b = "C:\"      'ファイルがあるパスを入れてください。
For a = 1 To 65536
    If Cells(a, "A") = "" Then Exit For
    If Trim(Dir(b + Cells(a, "A") + ".jpg")) = "" Then
        MsgBox "変換元 (" + b + Cells(a, "A") + ".jpg) は 存在しないのでリネームできません。"
    Else
        If Trim(Dir(b + Cells(a, "B") + ".jpg")) = "" Then
            Name b + Cells(a, "A") + ".jpg" As b + Cells(a, "B") + ".jpg"
        Else
            MsgBox "変換先 (" + b + Cells(a, "B") + ".jpg) は 存在するので 重複となりリネームできません。"
        End If
    End If
Next a

End Sub

そういうフリーソフトがあるかどうか分からないので、VBAで書いてみました。

Option Explicit
Const Path = "C:\写真\"
Dim r As Integer
Dim sour, dest As String

Sub hoge_rename()
    r = 1
    Do While Cells(r, 1).Value <> ""
        sour = Path & Cells(r, 1).Value & ".jpg"
        dest = Path & Cells(r, 2).Value & ".jpg"
        Name sour As dest
        r = r + 1
    Loop
End Sub

Excelシートに空行があったら終わるようにしてあります。

エラー処理はしていません。少なくとも、同名ファイルがあった場合の処理を加えておくべきです。また、A列に値があるのにB列に値がない場合の処理もしていません。

フリーソフトでの方法を紹介します。

リネームソフトは外部リストからリネームできるものならなんでもいいと思います。

ファイル名変更君

まず、リストを作るためにＡ列でソートし（既に連番でソートされている場合は必要ありません）

Ａ列を削除してＢ列だけを名前を付けて保存でテキストで保存します。

Ｂ列を選択してテキストファイルにコピーしてもいいです。

次に先ほどのファイル名変更君を実行し

フォルダ名を選択して取り込み。

リネーム方式をテキストとして、テキストファイルを先ほどのリストファイルに。

ファイル名のところをクリックしてソートして、実行です。

置換データが既にExcel上にあるのでVBAでリネームするのも簡単です。

具体的なコードではなく（自分で作るのが面白いので）処理手順だけ説明すると。

私ならば、FileSystemObjectを使います。（覚えておくといろいろ応用が利くので）

http://officetanaka.net/excel/vba/filesystemobject/index.htm

まず、FileSystemObjectを使うために、参照設定か下記のようにCreateObjectメソッドを使ってインスタンスを作成。

http://officetanaka.net/excel/vba/filesystemobject/first.htm

（参照設定のほうがインテリセンスを使えるのでお勧め。）

FileExistsメソッドを使ってファイルが存在するかを確かめて

http://officetanaka.net/excel/vba/filesystemobject/filesystemobj...

GetFileでファイルを取得し、Nameプロパティで設定します。

http://officetanaka.net/excel/vba/filesystemobject/file.htm#Name

これを1行目から最終行まで行います。

そういうときは 僕はVBAではなくて関数でやってしまいます。

（先ほど回答した「デジカメの画像を・・」というのと内容が少しかぶりますが・・）

(1) C1のセルに「="move " & B1 & ".jpg " & A1 & ".jpg"」と入れる

(2) C1のセルを選択した状態で、右下の「■」をクリックして下にドラッグ

　　⇒ そうすると数式が自動的に B1, B2, ... とカウントアップ(?)されます

(3) コマンドプロンプトで次のように打つ

　　cd C:\写真

　　※ コマンドプロンプトは「ファイル名を指定して実行」で「cmd」と入力すれば出ます

(4) C列をコピーして、コマンドプロンプトに貼り付ける。

※ その際「写真」フォルダは念のため、バックアップ（フォルダごとコピーする）してからにした方が良いと思います。