Thank you for your time and work. After two weeks (!) of wrestling and struggling, I have succeeded (I think*) in building and installing Alien::wxWidgets 2.9.4 on StrawberryPerl 5.16.3.
I must say that the road was strewn with pitfalls and gotchas.

For the benefit of the PerlMonks community, here is the story and the details:

1. Firstly, I wanted to use StrawberryPerl 5.16.3, since I've read some recent answer by Mark Dootson, that you need 5.16.3 for successful use of wxWdigets 2.9.4.
So I downloaded SB 5.16.3 64 bit (since I'm using Windows 7 64 bit), and installed it.
According to the documentation, in order to run side-by-side multiple Perl installations, all you need to do is to tweak the ENV variables so they should point to the right Perl installation. So, I did that.

2. First hitch: I have been using CPANPLUS (typing "cpanp" at the command prompt) to download and install modules. CPANPLUS now ships with standard Perl distributions, and is considered more user friendly and offering more functionality than cpan. It turns out that CPANPLUS has something called "indices cache" (whatever that is - I couldn't find any documentation for it), and if you don't refresh that cache, cpanp keeps pointing to the previous Perl installation. It took me a couple of days to find out that you have to type: "x" at the cpanp shell, in order to refresh that cache.
I did that. Then, in order to build and install wxWidgets 2.9.4, you need to enter some parameters (mainly the wxWidgets version number, 2.9.4) locally; so you can't just go: >i n at the cpanp prompt. (n is just an integer index number of the Alien::wxWidgets module in the cpanp search list). You need to go:   cpanp>z n.
This: a. downloads wxWidgets, b. expands the tarball, and c. opens a shell where you can enter the Perl build commands.
cpanp stores all of that at:
C:\Documents and Settings\YourUsername\.cpanplus\5.16.3\build\Alien-wxWidgets-0.64\.
Since this path contains spaces, it creates a big problem that we'll hit later on.

3. Anyway we go: perl Build.PL, and immediately hit the next hitch: "Cannot find the file specified":

if not exist gcc_mswudll mkdir gcc_mswudll
process_begin: CreateProcess(NULL, -c "if not exist gcc_mswudll mkdir 
+gcc_mswudl
+l", ...) failed.
make (e=2): The system cannot find the file specified.
gmake: [gcc_mswudll] Error 2 (ignored)
if not exist ..\..\lib\gcc_dll mkdir ..\..\lib\gcc_dll
process_begin: CreateProcess(NULL, -c "if not exist ..\..\lib\gcc_dll 
+mkdir ..\.
+.\lib\gcc_dll", ...) failed.
make (e=2): The system cannot find the file specified.
gmake: *** [..\..\lib\gcc_dll] Error 2
system: gmake -f makefile.gcc all  UNICODE=1 MSLU=0 BUILD=release SHAR
+ED=1  DEBU
+G_INFO=default DEBUG_FLAG=1 LDFLAGS=" -m32" CPPFLAGS="-m32": 512 at i
+nc/My/Buil
+d/Win32.pm line 274
[download]

doing extensive Googling, one finds that there is lots of stuff and advice in the NET about this problem; it turns out that it's a PATH issue (the script wrongly pulls-in some executables from a stray CPP compiler installation (cygwin?) on your system, instead of your StrawberryPerl's gcc). So I hacked PATH to contain only the system %windir% and the perl bin and lib directories. Once I did that, build charges ahead merrily for about 25 minutes, doing compilations and links.

4. Then we hit the next hitch I mentioned above: the "spaces in the dirname" problem:

\Alien-wxWidgets-0.64>perl build
Building Alien-wxWidgets
if not exist ..\..\lib\gcc_dll\mswu mkdir ..\..\lib\gcc_dll\mswu
if not exist ..\..\lib\gcc_dll\mswu\wx mkdir ..\..\lib\gcc_dll\mswu\wx
   -O2 -mthreads  -DHAVE_W32API_H -D__WXMSW__   -DNDEBUG    -D_UNICODE
+  
    -IC:\Documents and Settings\Helen\.cpanplus\5.16.3\build\Alien-wxW
+idgets-0.64\wxWidgets-2.9.4\lib\gcc_dll\mswu
    -IC:\Documents and Settings\Helen\.cpanplus\5.16.3\build\Alien-wxW
+idgets-0.64\wxWidgets-2.9.4\include
    -W -Wall 
    -IC:\Documents and Settings\Helen\.cpanplus\5.16.3\build\Alien-wxW
+idgets-0.64\wxWidgets-2.9.4\samples\minimal
    -DWXUSINGDLL 
    -IC:\Documents and Settings\Helen\.cpanplus\5.16.3\build\Alien-wxW
+idgets-0.64\wxWidgets-2.9.4\samples
    -DNOPCH   -Wno-ctor-dtor-privacy -m64 -Os -DNO_GCC_PRAGMA
objdump: 'C:\Documents': No such file
objdump: 'and': No such file
objdump: 
'Settings\Helen\.cpanplus\5.16.3\build\Alien-wxWidgets-0.64\wxWidgets-
+2.9.4\lib\gcc_dll\wxbase294u_gcc_custom.dll':
No such file
[download]

What I did then to workaround that: I opened a new directory: c:\build, and moved \Alien-wxWidgets-0.64 there, (whereby moving there everything below it).
Build, build test and build install then completed successfully.

5. The next step was to install Wx::. You go: cpanp>m Wx and you get a long list of modules, where, let's say, the number n corresponds to Wx::. You then go:  cpanp>i n. It then went into about 30 minutes of compilations and linkings, and then in the testing, it crashed with:

Problem Event Name:    APPCRASH
  Application Name:    perl.exe
  Application Version:    0.0.0.0
  Application Timestamp:    513f0ec4
  Fault Module Name:    wxbase294u_gcc_custom.dll
  Fault Module Version:    2.9.4.0
  Fault Module Timestamp:    518e8f2c
  Exception Code:    c0000005
  Exception Offset:    000000000004cc55
  OS Version:    6.1.7600.2.0.0.256.1
  Locale ID:    1033
  Additional Information 1:    1c08
  Additional Information 2:    1c088a33d2f6bb66ead4dd52958c47ec
  Additional Information 3:    ddec
  Additional Information 4:    ddec72cc39270964f7a59fd6c1d39e4c
[download]

and here is the part in the log where it occurred:

...
F:\Win7programs\SBPerl\perl\bin\perl.exe -MExtUtils::Command -e cp -- 
+script/wxperl_overload blib\script\wxperl_overload
pl2bat.bat blib\script\wxperl_overload
[ERROR] [Tue May 14 03:43:31 2013] MAKE TEST failed: F:\Win7programs\S
+BPerl\perl\bin\perl.exe "-MExtUtils::Command::MM" "-e" "test_harness(
+0, 'blib\lib', 'blib\arch')" t/*.t
[HISTORY] [Tue May 14 03:43:46 2013] Proceed anyway? [y/N]:  y
[MSG] [Tue May 14 03:43:49 2013] Files found in blib\arch: installing 
+files in blib\lib into architecture dependent library tree
...
[download]

Amazingly, cpanp came back then and asked whether to ignore it and continue. I answered "yes", and it completed the installation.

Things seem normal now; when I go: >perl -MWx -le " print join q/ /, $Wx::VERSION, Wx::wxVERSION_STRING "
I get: 0.9922 wxWidgets 2.9.4.
Several applications I have using wxWidgets are behaving normally.

I hope I don't have a broken module somewhere, or a broken wxWidgets class lurking somewhere, that in the future will break exactly at the wrong moment.
Update: Indeed, the problem (apparently in wxbase294u_gcc_custom.dll) has already showed up here: wxPerl: attempting to install Wx::Demo crashes perl.exe

So markwx (and all knowledgeable Monks), I'd like to ask you the following questions:

1. Can I re-test Alien::wxWidgets and/or Wx::, in order to pinpoint whether there is a broken module or class somewhere?
2. Using  cpanp> z Alien::wxWidgets to do the installation, is there a way to configure CPANPLUS and tell it to set a different build directory (to workaround the "spaces in the path" problem?)
3. Can you explain the way to overcome the PATH problem? (in section 3 in the story above - that's different from the spaces issue)?