syntax_fix を使うと一瞬でした。
(defun query-replace-ruby-18-to-19-stayle-hash (&optional delimited start end)
"Rubyの 1.8 スタイルの Hash を 1.9 から導入されたスタイルへ確認しながら変更する ネストした hashには対応していない"
(interactive)
(query-replace-regexp ":\\([^ ]+\\) => \\([^ ]+\\)" "\\1: \\2" delimited start end))
という正規表現を指定しただけの Emacs Lisp も書いたけどみなかったことにしてください。