J’écrirais : je ne les ai jamais cru capables car croire porte sur capables et pas sur « les » qui n’est pas COD.
La phrase correspond à : je n’ai jamais cru qu’ils étaient capables. Capables est attribut de les (agent)

Contrairement à ce qui est dans la phrase suivante :
Ils m’ont raconté une histoire ; je ne les ai pas crus.