I'm just wondering, without a trusted third party, how can someone trust the maker of these bills that the private key is really under the hologram?
Impossible to know. When you buy physical bitcoins off someone you are putting your trust into them.
The code to create the PDF will automatically generate the keypair and put the QR codes into the bill. It would take modifying the code to remove the private key. Though the printer could also scan the private key themselves to steal them (or also modify the code to make it record them).
That said, when the details of the algorithm are solid and can be translated into php or a bash script, I will be incorporating 3rd party private key addition to the bills (you would print a sheet, sticker it, send it to someone else to print over keypair two and they would sticker and cut it).
So what you're saying is there is no guarantee to their value, which makes them essentially worthless by virtue of being totally unreliable. good job.