Hmmmm. Now you've stumped me. Have you tried dropping and re-creating the stored procedure? Don't ask my why, but I've seen that fix other unexplained errors.
Try using the 3 part naming convention for all of your tables in the stored procedure. I wonder if it can't find them because it's looking in master. Just a thought, probably won't work.
"Even if I change it to a regular table I get the same error type"
Are you creating the table before the SProc runs, or doing an SELECT * INTO dbo.TransPayroll - maybe the table has to exist before the SProc starts
I don't know if this is wrong, but I don't use "dbo." when I use temporary tables:
FROM dbo.#TransPayroll
By the by, I would create the #TransPayroll table and then INSERT INTO it - that way you can put a PK on it, which in my experience makes the thing run a lot faster