If a given version of Perl can be built and installed with your particular C compiler, it should be able to be embedded as well.

You might consider test-building a Perl version that is still within the Perl p5p support window, which I think (now that 5.20 has been released) is probably Perl 5.18.2 or newer. perlpolicy suggests that the two most recent stable versions (5.20 and 5.18 at time of writing) are supported, and "critical security patches" are handled (to the best of p5p's ability) for Perl versions going back 3 years (this would therefore include 5.16, but probably not 5.14, since its initial release was May 14, 2011).

If you're stuck with Perl 5.8, make it 5.8.9, which at least has all the bug patches that any version of 5.8 will ever get.