Wierd. Should work. All needed should be in that dir...C:\Perl\lib\CORE... I forgott to add the link to that lib for the linker, but this _should_ be working!
gcc.exe "C:\test\start.c" -o "C:\test\start.exe" -I"C:\Dev-Cpp\include" -I"C:\Perl\lib\CORE" -L"C:\Perl\lib\CORE" -L"C:\Dev-Cpp\lib"
Notive the -L"C:\Perl\lib\CORE" part. Also, the perl58.lib is there. Aswell as PerlEz.lib.