"Who should I be reporting to?"
I have always reported to the 'VP of operations' or the 'general manager' or someone like that. I've never reported to a production employee. I've always been 'equal' to the top person 'on the floor' from the production side of things. We (the top production person and I) would report to the same boss.
It is VERY important that the person you both report to understands food safety and it's importance. This person can't just be a production only person. If so, you're in for trouble.
"I often go through audits with regulators and make corrective actions that are rebutted by the Production Manager even though multiple auditors agree the CAR is a good fix. Is this ok?"
No, this is bad. It's possible, of course, that they might have other ideas on how they can implement your corrective action without being as disruptive to their schedule. For example, you might determine the ultimate fix to a problem is to invest in a new piece of machinery. Production might counter and say that they aren't going to get the budget for that so they'd like to implement a more frequent cleaning schedule or something like that. You need to work with them too, but at the end of the day, you're the 'end of the line' in food safety and the company needs to understand that you're doing these things because they need to be done.
As everyone else said, if your senior management (your bosses boss) doesn't understand your role and back you up, you're going to have a tough go of it and, honestly, your job probably isn't worth the headache you will have and you should start looking for something else. Senior Management Commitment is a big deal.
"Should I train all employees on documentation, GMP's, CCP's etc.. or should it be done by production or both?"
You are the trainer. You train on all the food safety things you want to train on. Production can perform 'task' training - how to set up the machine, how to operate the control panel, etc.
"There is a lot of tension between departments, It's even affecting my health, I love my job, but management seems to side with Production instead of sound food safety, please help."
Time to look for a new job.