Partons de cette base : il exhorte Paul à revenir, il demande avec insistance à Paul de revenir. Il y a en principe un COD, qui est la personne à qui on s’adresse.
On peut souvent vérifier la possibilité de différentes constructions d’un verbe dans le dictionnaire TLFi.
Ce dictionnaire n’autorise pas les fautes syntaxiques, mais recense cependant les usages rares mais acceptables. Ainsi, la page du verbe « exhorter » mentionne plusieurs constructions, plusieurs usages.
Vous commencerez par constater que exhorter à quelqu’un n’existe pas, et qu’il n’est donc pas question de leur exhorter.
La construction normale est d’exhorter quelqu’un, et donc de les exhorter.
Un usage absolu est recensé (A.1.abs.). Selon moi ce n’est pas réellement un usage absolu, il s’agit simplement d’exhorter quelqu’un sans préciser qui, comme quand on dit qu’on mange sans préciser ce qu’on mange. Mais bon, l’usage sans complément est recensé, et là se trouve sans doute la réponse à votre question. Peut-on exhorter sans dire qui on exhorte ? Généralement non selon mon expérience, mais possiblement oui selon l’exemple du TLF.

Mon avis est que si cette phrase n’est pas de vous, si elle vient de quelqu’un qui parle correctement, il vous faut l’accepter, mais qu’en revanche il ne serait pas normal qu’à la fois cette phrase soit de vous et qu’elle vous chagrine.
Personnellement, j’aurais ajouté le COD « les » (il les exhorte). Le dictionnaire permet l’absence de complément (il exhorte). Ce qui est certain, c’est que vous ne pouvez pas ajouter le COI « leur » (il leur exhorte).