まとめると？

元シートの内容に列を追加したものを新規シートとして作成し、シート名を変更すればよいのでは？

問題の挙動

以下のようなurlsシートがsample.xlsxに存在するものとする。

	A	B	C
1	Google	Yahoo	%空白セル%

リンクの追加は以下の操作で行われているものとする。

セルを右クリック > リンク
アドレスにリンク先アドレスを入力してOK

上記のファイルに対して、以下のようなコードでBに新規列を追加した。

import openpyxl

# sample.xlsxファイルを開き、urlsシートを選択する
workbook = openpyxl.load_workbook("sample.xlsx")
sheet    = workbook["urls"]

# B列の挿入
sheet.insert_cols(2)

# 編集内容を保存する
workbook.save("sample_insert_col.xlsx")
workbook.close()

すると、以下のように「列挿入されたもののリンクの座標は変更されない」xlsxファイルが生成された。

	A	B	C
1	Google	%空白セル%	Yahoo

(かなり強引な)回避方法

シートに対して編集すると意図しない挙動をするのであれば、別シートを新規に作成/出力して、元シートを削除すればよい、という考え。

import openpyxl
from copy import copy, deepcopy

# sample.xlsxファイルを開き、urlsシートを選択する
workbook = openpyxl.load_workbook("sample.xlsx")
sheet    = workbook["urls"]

# B列の挿入
# sheet.insert_cols(2)


# 元シート名を変更
sheet.title = "urls_original"

# 元シートのセルの値を取得
cel_A1 = sheet["A1"]
cel_B1 = sheet["B1"]

# 新規シートを作成
new_sheet = workbook.create_sheet("urls")

# 元シートA1の内容を新規シートA1にコピー
new_sheet["A1"].value = cel_A1.value
new_sheet["A1"].hyperlink = copy(cel_A1.hyperlink)
new_sheet["A1"].font = copy(cel_A1.font)

# 新規シートでB1に関する処理を行わないため、列挿入した状態と同じになる

# 元シートB1の内容を新規シートC1にコピー
new_sheet["C1"].value = cel_B1.value
new_sheet["C1"].hyperlink = copy(cel_B1.hyperlink)
new_sheet["C1"].font = copy(cel_B1.font)

# 元シートを削除する
del workbook["urls_original"]

# 編集内容を保存する
workbook.save("sample_insert_col.xlsx")
workbook.close()

上記で実行したところ、以下のようになった。

	A	B	C
1	Google	%空白セル%	Yahoo

泥臭い回避もたまには有効

openpyxlの仕様上回避が難しかったのでこのようなコードになった。
成果物は想定通りのため、取り急ぎこれで対応してみるのもありかもしれない…。