Leur devant un verbe est invariable : je leur parle (à eux).
Ils ont pris leurs affaires : leur devant un NC pluriel se met au pluriel.

Le singulier de « leur » pronom personnel est « lui » :
Je leur avais amené ma petite sœur.
Je lui avais amené ma petite sœur.

Ni par tout autre chose que je leur avais amené(e), je ne sais pas si c’est très français. Prenons une formulation qui me parait plus claire : Je leur avais amené (apporté) tout autre chose / une tout autre chose.

Tout autre chose est un pronom indéfini masculin singulier (invariable), le participe passé par conséquent reste au masculin singulier :
C’est tout autre chose que je leur avais amené / C’est une tout autre chose que je leur avais amenée.

Bonsoir,

je pense qu’ici nous devrions écrire « toute autre chose », car il ne s’agit sans doute pas de la locution adverbiale, mais de « n’importe quelle autre chose ». Dans ce cas, « tout » est adjectif et s’accorde.
Je cite : http://www.parmotsetparvaux.fr/cpmf/cpmf59.html

« Certes, il est quelquefois fondé d’accorder tout. Pour peu que vous signifiiez par là « n’importe quelle autre chose » ; pourvu, donc, que tout soit un adjectif indéfini, rien ne s’oppose (au contraire !) à ce qu’il prenne la marque du féminin. « Venant de lui, toute autre chose nous eût étonnés » n’a évidemment rien que de très correct. Mais si tout tient lieu d’adverbe et peut être remplacé par entièrement, complètement, tout à fait, l’invariabilité est de rigueur. »

Ex : Les enfants n’ont été séduits, ni par ce gâteau, ni par toute autre chose que je leur avais amenée.

Dans ce cas, on doit aussi accorder le participe passé avec son COD « chose » puisqu’il est placé avant. Donc, « amenée » est juste.
L’accord n’a rien à voir avec « leur », qui est un pronom COI (à eux).

Cdlt

Merci pour vos réponses instructives !