What I was trying to do is to avoid the sheer horror of using Win32::API by nicely mapping these functions to readdir().

I think the only option you currently have which comes close to that is to enable the deprecated compile-time option USING_WIDE in win32.h in the Perl sources (which still works in 5.8.8, but won't any longer in 5.10). Also see Japanese filenames and USING_WIDE in win32.h, if you haven't come across this thread yet.