Ruby 2系ではruby-debug19ではなく、byebugを使うのがいいと思います。(というか、それしか使えないはずです)
Gemfileを書き換えて、再度bundle installしてみてください。
参考リンク
追記
その後再度bundle installしたところ次はmysql2でエラーになりました。
長いYak shavingの始まりかもしれませんね。
確かに bundle update mysql2
のようにすれば解決するかもしれません。(未確認)
mysql2の問題が解決しても、今後も繰り返し新しいエラーが発生するかもしれません。
その場合は bundle update xxxx
のように、エラーになったgemをアップデートしていくとうまくいく可能性があります。
依存関係の問題でbundle updateできないと怒られた場合は、bundle update foo bar
のように複数のgemを同時にアップデートしてください。
ただし、考えなしにgemをアップデートしていくと、互換性のない変更が取り込まれて今度はRailsが起動しなかったり、実行時エラーが発生したりするかもしれません。
gemのバージョン番号が大きく変わったときはそのあたりも注意してください。
(一番良いのはシステムの機能を網羅的に検証するテストコードが用意してあり、問題を自動的に検出できるようにしておくことです)
RubyやRailsのバージョンアップは何かと苦労を伴うものです。
プロジェクトの構成によって発生する問題と発生しない問題が無限にあるため、唯一の正解はありません。
エラーが起きたらネットの情報を調べたり、gemのコードを追いかけたりしながら、できるだけ自力で解決できるスキルを養っていくのが良いと思います。