The only sane approach is to use utf8;, and to decode the strings that DBI returns with Encode::decode_utf8, unless your DBD::mysql does that for you already.

I have no experience with tr and Unicode, but s/// works fine.

When you want to print out stuff, you also need binmode STDOUT, ':encoding(UTF-8)'; or similar stuff.

See also encodings, Unicode and Perl, perluniintro and perlunifaq.

Update: And take a look at Text::Unidecode, it might safe you quite some work.