You really should be using perl 5; perl 4.036 hasn't been updated since 1992 and is considered "dead".
Run Configure, and use the solaris_2_0 hints, don't use the solaris_2_1 hints and don't use the config.sh you may already have. First you must make sure Configure and make don't find /usr/ucb/cc. (It must use gcc or the native C compiler: /opt/SUNWspro/bin/cc)
Some questions need a special answer.
Are your system (especially dbm) libraries compiled with gcc? [y] y
yes: gcc 2.3.3 or later uses the standard calling conventions, same as Sun's C.
Any additional cc flags? [ -traditional -Dvolatile=__volatile__ -I/usr/ucbinclude] -traditional -Dvolatile=__volatile__Remove /usr/ucbinclude.
Any additional libraries? [-lsocket -lnsl -ldbm -lmalloc -lm -lucb] -lsocket -lnsl -lm
Don't include -ldbm, -lmalloc and -lucb.
Perl 5 compiles out of the box and comes preinstalled with Solaris 8 and later.