Package MagickCore was not found in the pkg-config search path

I have the the same problem. This work for me (Ubuntu):

sudo apt-get install libmagickwand-dev

This just solved the issue for me (works on ubuntu 18.04):

sudo apt-get install libmagick++-dev

rmagick gem is not able find PKG_CONFIG_PATH while installing. We need to tell where the path for the ImageMagick exists. It's always better to add in the bash.

export PKG_CONFIG_PATH=/usr/local/Cellar/imagemagick/6.9.3-7/lib/pkgconfig