I've installed Visual C++ Express

You might not have to do that - in fact you can probably use Strawberry's gcc compiler and dmake (even though you're not using Strawberry Perl).
But, firstly, could you provide the output of perl -V (that's upper case "V").

I can see is specified in the MakeFile - CC = icl

You can change that easily enough by starting a fresh build (from scratch) with perl Makefile.PL CC=cl instead of just perl Makefile.PL
Or, if you prefer, just amend the current Makefile to specify CC=cl and then re-run nmake.
In fact, try that first - it might just work ... or it might need additional tweaks.

Cheers,
Rob