You seem to have already found the appropriate module: Win32::Shortcut.

For others reading this discussion, and for future reference, Perl in a Nutshell has a small section on this module. At least for the moment, this is available online for free on Safari Bookshelf. As of the second edition, the appropriate section is 22.18, with the entire 22nd chapter of the book being on Win32.

From the book above, I learned that the following code will print the Target and Start In values you wanted:

$link = new Win32::Shortcut();
$link->Load("test.lnk");
print "Target: $link->{Path} $link->{Arguments}\n";
print "Start In: $link->{WorkingDirectory}\n";
[download]