Ok, so this is what I have: We can use the -hidemargin to force image in menuitem (using Tk::Compound) to the far left.

There are two major problems left:

1) Image used in menuitem does not appear properly before it is hoovered over by mouse pointer.
2) "Hook" of checkbutton now has disappeared. Where did it go?

Example code demoonstrates these issues.

#!/usr/bin/perl -s

use Tk;
use Tk::ToolBar;
use Tk::Compound;
use strict;

my $mw = MainWindow->new();

#Load images from Tk::ToolBar.
my $tb = $mw->ToolBar();
$tb->destroy();

my $compound = $mw->Compound;
$compound->Image( -image => 'acthelp16', -anchor => 'w' );
$compound->Space( -width => 8 );
$compound->Text( -text => "Open", -underline => 0 );
$compound->Space( -width => 28 );

my $menubar = $mw->Menu( -type => 'menubar', );

my $c2 = $mw->Compound;
$c2->Space(-width => 40);

$menubar->cascade(
  -label     => 'File',
  -tearoff   => 0,
  -menuitems => [ 
           #Problem 1: Image is now shown properply before we 
           #hoover over menuitem.
         [ Command => 'Open', -image => $compound, -hidemargin => 1, ]
+,
         '-',
           #Problem2: When we are using hidemargin, the "hook"
           #of the checkbutton doesn't appear anymore.
         [ Checkbutton => 'Checkthing', -hidemargin => 1, -image=>$c2,
+ -compound=>'left',  ],
                ]
);

$mw->configure( -menu => $menubar );
MainLoop;
[download]

Update:
Ok, I've figured this out now. It appears that we have to set up an after timer with -postommand to configure images as menu is shown to get them to display correctly. This is might be bug on win32 only!? Bitmaps seems to display fine without this hack.

CheckButton indicator is removed when -hidemargins is enabled. Nothing to do about that. Solution for me is to move all CheckButton menuitems to a seperate cascade menu where we turn off -hidemargins and populate with CheckButton menuitems only.

Update (for later reference):
Ok, seems like xpm images, created with the Pixmap()-method, work ok with menus on win32. Then we can avoid "-postcommand fix" ,which create ugly flash when many icons are used, and use icons with lots of colors (unlike bitmaps).
Tools "any to icon"/"icon to any" can convert images to .ico/xpm-files.