First of all, you should instruct Win32::OLE to use unicode, with the following 2 lines:

use Win32::OLE qw(CP_UTF8);
Win32::OLE->Option(CP=>CP_UTF8);
[download]

Secondly, it is not good to use obsoleted Unicode::String and Unicode::Map modules, it was used when Unicode in Perl was weak, now you should go other, the robust way, of perl5.8.x

I have scripts using Unicode::String and MSWord, so can share chunks of code on this

BR,
Vadim.