In case every single part in between the ESC sequences does conform to an encoding that can be handled with Encode::decode, the approach suggested by Jenda seems very reasonable.

Otherwise, if you need more arbitrary mapping facilities, I don't think there's anything fundamentally wrong with the approach you implemented :) - as long as you don't need arbitrary multibyte-to-multibyte mappings (OTOH, you do mention "...the byte sequence \xE0\x65 may represent one character" ...). In the latter case, the '.' in your substitution regex might become a little unwieldy. For singlebyte-to-multibyte mappings though (like "legacy" to UTF-8), it seems fine to me.

For more complex requirements, it might ultimately turn out to be easier to use a proper parser (e.g. Parse::RecDescent), but YMMV.