I don't have a PC to test it on at the moment, so I can't tell you exactly where it is, but I do know two things:
1. There *is* a copy of the interpreter bundled by default in PAR exe files.
2. You can create your PAR exe, then unzip it with whatever you use for .zip files, and look at the directory structure. As I understand it, and hopefully someone will correct me if I'm wrong, the cwd when the .exe file is running will the the top level of that directory structure. You should then be able to modify that BEGIN line with the relative path of the interpreter and make it work. Well, that and taking out the "#" that's making it a comment. :)
Again, I can't test this but I think it should work or at least put you on the path to.... errmm.... workitude?