L'idea e' sempre quella, md5(pack('H*','4d724861686e'));

Ti spiego meglio il problema del tuo approccio: il carattere "è" utf8 in esadecimale e' c3a8
Se tu prendi la stringa 2 caratteri alla volta, non otterai da c3a8 indietro 1 carattere è, ma otterrai 2 caratteri nuovi.
Pero' se non avrai mai in input caratteri non-ascii, allora il problema non si pone, puoi continuare a prenderli 2 alla volta