"you suggested that I needed to install Image::Magick"
Close, but I didn't say that. I actually suggested you install the ImagMagick software.
Image::Magick is not a dependency of Image::OCR::Tesseract. Image::Magick is an interface to ImageMagick.
Image::OCR::Tesseract uses one of the executables which make up the ImageMagick distribution.
Install ImageMagick and try to build Image::OCR::Tesseract. Report any problems. Incidentally, to install Image::Magick you need to have installed ImageMagick, as specified in the documentation.
Update: fixed formatting.