What to say in PhD application when potential advisor is moving to another university?
which means that he will not be able to give input into PhD applications to university B


This is incorrect. He certainly can, if he chooses, e-mail the director of graduate admissions at B, say that he's interested in working with you, and ask him/her to consider your application favorably. They don't have to admit you, but that would be true even if he were at B now and had been there a long time.

I'd recommend mentioning this in your SOP, and perhaps also e-mailing him and letting him know that you are applying to B with the idea of working with him. (If you have not done so already.)

That said, "I am quite sure I would have been admitted to university A had he remained there" sounds possibly a bit presumptuous, although I don't know your circumstances. In any case, do what you would have done if this professor wasn't moving: apply to the graduate program where he'll be, let him know, and hope for the best. Good luck.