When I visited your web page (http://tech-nikos.gr/cgi-bin/test.pl), I was able to get a sensible display by telling my browser to treat the page as iso-8859-7 (greek). But I gather you want the text to be in utf8, which I think would be a good idea.
As you follow moritz's good advice, you have to respect the docs regarding Encode::from_to(). Here's an easy way to do the required loop in a single line of code:
Encode::from_to($_, 'ISO-8859-7', 'utf8') for (@menu_files);
The reason why the path strings are showing up fine is because they are just plain ascii characters; it's only the file names that are non-ascii, and if the web server and browser don't agree on what the encoding is for those non-ascii characters, it's just noise.
(updated to fix grammar in first sentence)