Unfortunately, the answer is very much "it depends".
If the employee's contract stipulated that work involving such checks would be necessary, or it could be argued that the employee should already have had these checks / documents in place, then there's at least some argument to say it's not really infringing on his rights to make him take personal leave to sort the problem out. If the above doesn't apply, then yes, I'd say the company should be paying for the time required to sort this out (he is getting them filled out solely for the purposes of the company after all.)
Resolving the situation really depends on how much aggravation he's prepared to cause over half a day's leave. I'd certainly start by gently pushing back to the manager, saying something akin to:
I know you've asked me to take this as personal leave, but since I'm sorting out paperwork that's only ever required for tasks at this company, I feel it should be paid for as company time. Is there no way we can work this out without me having to sacrifice some leave to get this sorted?
At that point there's every chance he may relent, realise that it's an unreasonable request and just tell you not to worry about it.
If he doesn't, then your next option is to put a more formal email together with the chain of events and email HR explaining that you don't feel this should count against your annual leave entitlement - but this may get your manager's back up, so it depends very much on where you want to draw the line on this.