Cannot install rmagick after server update

I'm running a debian server and upgraded all packages after quite a while (apt-get update, apt-get upgrade, apt-get distro-upgrade). Then rmagick didn't work anymore becuase imagemagick was updated.

So I ran:

gem uninstall rmagick
bundle install

Then I got this:

Gem::Ext::BuildError: ERROR: Failed to build gem native extension.

    /usr/local/bin/ruby extconf.rb
checking for Ruby version >= 1.8.5... yes
checking for gcc... yes
checking for Magick-config... no
Can't install RMagick 0.0.0. Can't find Magick-config in /usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games

*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of necessary
libraries and/or headers.  Check the mkmf.log file for more details.  You may
need configuration options.

Provided configuration options:
    --with-opt-dir
    --without-opt-dir
    --with-opt-include
    --without-opt-include=${opt-dir}/include
    --with-opt-lib
    --without-opt-lib=${opt-dir}/lib
    --with-make-prog
    --without-make-prog
    --srcdir=.
    --curdir
    --ruby=/usr/local/bin/ruby

extconf failed, exit code 1

Gem files will remain installed in /srv/www/www.example.com/shared/vendor/bundle/ruby/2.1.0/gems/rmagick-2.13.3 for inspection.
Results logged to /srv/www/www.example.com/shared/vendor/bundle/ruby/2.1.0/extensions/x86_64-linux/2.1.0-static/rmagick-2.13.3/gem_make.out
An error occurred while installing rmagick (2.13.3), and Bundler cannot continue.
Make sure that `gem install rmagick -v '2.13.3'` succeeds before bundling.

This is cat mkmf.log:

    checking for Ruby version >= 1.8.5... -------------------- yes

--------------------

find_executable: checking for gcc... -------------------- yes

--------------------

find_executable: checking for Magick-config... -------------------- no

--------------------

Can't install RMagick 0.0.0. Can't find Magick-config in /usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games

Can anyone help me with this?

— UPDATE 1 —

After installing some graphicsmagic stuff, I got a little further:

apt-get install graphicsmagick-libmagick-dev-compat
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  libmagick++-6-headers libmagick++-6.q16-dev
Use 'apt-get autoremove' to remove them.
The following packages will be REMOVED:
  libmagick++-dev libmagickcore-dev
The following NEW packages will be installed:
  graphicsmagick-libmagick-dev-compat
0 upgraded, 1 newly installed, 2 to remove and 1 not upgraded.
Need to get 0 B/26.2 kB of archives.
After this operation, 267 kB disk space will be freed.
Do you want to continue? [Y/n]

This is bundle install output:

checking for Ruby version >= 1.8.5... yes
checking for gcc... yes
checking for Magick-config... yes
checking for ImageMagick version >= 6.4.9... yes
checking for stdint.h... yes
checking for sys/types.h... yes
checking for wand/MagickWand.h... no

Can't install RMagick 0.0.0. Can't find MagickWand.h.
*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of necessary
libraries and/or headers.  Check the mkmf.log file for more details.  You may
need configuration options.

Provided configuration options:
    --with-opt-dir
    --without-opt-dir
    --with-opt-include
    --without-opt-include=${opt-dir}/include
    --with-opt-lib
    --without-opt-lib=${opt-dir}/lib
    --with-make-prog
    --without-make-prog
    --srcdir=.
    --curdir
    --ruby=/usr/local/bin/ruby

extconf failed, exit code 1

Does this help us in any way?

* — Update 2 — *

After installing graphicsmagick-libmagick-dev-compat and libmagickcore-dev separately, I tried to install libmagick++-dev

apt-get install libmagick++-dev
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be REMOVED:
  graphicsmagick-libmagick-dev-compat
The following NEW packages will be installed:
  libmagick++-dev
0 upgraded, 1 newly installed, 1 to remove and 1 not upgraded.
Need to get 0 B/121 kB of archives.
After this operation, 115 kB of additional disk space will be used.