What you're looking to do is far from trivial, however....
Lets simplify first. Forget the pdf module, I assume you want to render your embed (and any other) tags and push the result into your pdf document (or anywhere else). In short you want EE Template in, Html Out.
We can actually achieve this prior to the PDF creation, and avoid heavy modification of the module, after all you don't know how they could be parsing in the module, in the best case it'll be a normal tag renderer but as the parse order shows the Shine PDF tag will be processed long before your embed.
So, with some clever PHP you can re-use the EE Template engine, we can render the EE template using the Template engine and output it onto the template before the module tags, like so :
PHP on parsed on input
<?php
//this is the template code you wish to parse early into the pdf
$str = "{embed='group/template' embedvar='true'}";
ee()->TMPL->parse($str);
?>
{exp:shine_pdf:make}
<?php echo $str; ?>
{/exp:shine_pdf:make}
This should parse the $str
as if it was part of the template you are on at the moment (so your globals, variables etc should be available).
This is untested please note, so you may have to debug, however the concept is sound (used it before). Also note I've never used Shine PDF before but I'm assuming its a case of 'put your content between the tags', so I've put {exp:shine_pdf:make}
tags in for example.