items() で辞書から要素を取り出し、random.choice でランダムに要素を選択する。
例
import random
# 県庁所在地
mydict = {'宮城県':'仙台市','茨城県':'水戸市','島根県':'松江市','兵庫県':'神戸市','愛媛県':'松島市','沖縄県':'那覇市'}
# print(mydict)
first, second = random.choice(list(mydict.items()))
print('選択結果: '+first+' '+second)
結果
選択結果: 島根県 松江市