/bin/sh: cc_r: not found

You need a C compiler — more specifically, the IBM® XL C/C++ compiler (part of which is the cc_r program), because that's what your Perl binary has been built with.

That said, an easier/cheaper way out would probably be to use the pure-Perl variant Digest::MD5::Perl instead.  It is significantly slower, though, but depending on how much data you actually need to compute digests for, this might be a non-issue...

Alternatively, you could build your own perl from scratch with the free gcc compiler, in which case you could then build extension modules with the same compiler.