At the end of the day there has to be a lookup. That can be fairly quick using the translation function:

use warnings;
use strict;

my $str = <<'STR';
Les naïfs ægithales hâtifs pondant à Noël où il gèle sont sûrs d'être 
+déçus et
de voir leurs drôles d'œufs abîmés
STR

my %xlateL = (
    a => 'âà',
    c => 'ç',
    e => 'èëéê',
    i => 'ïî',
    o => 'ô',
    u => 'ùû'
    #...
    );

my %xlateU;
$xlateU{uc $_} = uc ($xlateL{$_}) for keys %xlateL; #Generate the uppe
+r case versions

eval "\$str =~ tr/$xlateL{$_}/$_/;" for keys %xlateL;
eval "\$str =~ tr/$xlateU{$_}/$_/;" for keys %xlateU;

print $str;
[download]

Prints:

Les naifs ægithales hatifs pondant a Noel ou il gele sont surs d'etre 
+decus et
de voir leurs droles d'œufs abimes
[download]

Note that æ causes a little grief however. Using a regex rather than the translation and a seperate set of tables is probably the fix for that.

This would make a good CPAN module when you've got it done. :)