Step 1: Next time you go to visit the payroll guy, do it during work hours. Pick a time on Friday, and just sit in his office until you have the cheque in hand. If you work on a laptop, bring your laptop with you, and just camp out in his office, so your boss can't accuse you of shirking your duties.
Step 2: Record whatever he says. Your locale may vary, but some locales permit recording of conversations, and if you can legally record the conversation, you should do it, just to get proof of the excuse for not paying you on time. Otherwise, take notes (on the laptop you brought with you to do your work on!) of what he said after the fact. Once again, make sure not to leave the office without your cheque in hand!
Step 3: Do not engage him in conversation. If he starts trying to change the subject, just direct it back on course. Something like this:
You: "Hey, I'm just here to pick up my paycheque, is it ready?"
Payroll guy: "Not yet. Hey, how about Joe in sales? He seems pretty gay right? What do you think?"
You: "Yeah, I dunno about that. Anyway, back to my paycheque, when will it be ready?"
Payroll guy: "Yeah, did you see what Joe did the other day, hitting on Brad?"
You: "Hm, that's nice. Now can we talk about my paycheque?"
etc. If this sort of banter continues, then you can begin threatening:
Payroll guy (after a while of conversation): "I heard Joe has a new boyfriend."
You: "Look, man. I'm just here to pick up my paycheque. My pay day is today, and I need the money. I don't want to talk about if Joe is gay or not, that's not my business, nor is it yours. Now, I'm going to sit here do my work while I wait for you to hand me my cheque, but the first thing I'm going to do when I open my laptop is email your direct line manager, CC the company president, and tell them I'm in your office right now while you're shirking your legal responsibilities as the payroll department for the company, and ask them to come join us so we can all work this out together as a nice cohesive team. Now, are you going to process my paycheque or not?"
Step 4: If you walk into the office and get any response other than "here's your cheque, thank you very much have a nice day", contact your local labour standards office ASAP. Don't threaten to do it, don't accuse anyone, don't start a confrontation. Just do it. The office will tell you what further documentation you need to file a case; maybe you need attestations from other employees, maybe you need to show a pattern of misbehaviour, etc. But they will tell you what you need and you should start collecting it.