(What I'm trying to do with all this is implement Paj's JavaScript MD5 library in Perl, ...)

Your bit fiddling question is certainly an interesting one, and I don't want to spoil the fun... but in case you just want to get the job done, you could also use the existing Digest::MD5 core module:

$ perl -MDigest::MD5=md5_hex -E 'say md5_hex("message digest")'
f96b697d7cb7938d525a2f31aaf161d0
[download]