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