I wouldn't be too concerned about it. You aren't hiring him to work on a whiteboard; you're hiring him to work at a keyboard. The whiteboard is an in-interview technique to help demonstrate his competence. If that doesn't work well for him, but he's able to demonstrate his competence in other ways, then that's an irrelevant implementation detail.
From what you've written, he seems to be good at communicating and working through problems, and you noted that he was able to accomplish the required work on a notepad. This solves the same problem as the whiteboard does: it gives the candidate somewhere to work through the process more slowly than typing, and without a Backspace key, while the interviewer watches to get a feel for their thought process. From what's written here, I don't see any good reason not to hire him based on this.