(This command simply creates a new image file called ÄÖÜß.gif with the text ÄÖÜß written as text in the image) ... however the file it create is named wrong and the content is wrong (both Ž™šá).

Ž™šá is exactly what happens if ÄÖÜß is encoded to cp850 ("OEM" encoding on Windows, used in console) and then wrongly decoded as cp1252 ("ANSI" encoding on Windows, used in ANSI versions of WinAPI).

I think that for system you'll need Encode::Locale's "locale" encoding, as opposed to "console_out": while text for console input/output should be encoded to OEM encoding (CP850 on a German system, CP866 on Russian one), file names and commands for system should be encoded in ANSI character set (CP1252 on a German system, CP1251 on Russian, etc.). You can also try to search for Unicode-related WinAPI wrappers for Perl (Does Win32::Unicode work? Is Win32::Process Unicode-aware?), but I can't give any advice on them.

In conclusion, try:

use utf8;
use Encode 'encode';

my $str = "convert -size 100x25 -background white -fill black -pointsi
+ze 25 label:ÄÖÜß ÄÖÜß.gif\n";

print encode cp850 => $str;
system encode cp1252 => $str;
[download]

(or: use Encode::Locale; print encode console_out => ...; system encode locale => ...; so your program is portable across different locales in Windows, though finding a way to use W-suffixed WinAPI functions would be better)

Since you are using ImageMagick, you can try its Perl binding, although getting Strawberry Perl to build it was not an easy task last time I tried it.