Well, then, maybe it comes from Win32::GuiTest, which is not explicitly described as Unicode compliant.
Since you're using the utf8 module, you can try (untested) :

SendKeys(utf8::upgrade('$your_string'));
[download]

Hope this works.