La construction pronominale est ici accidentelle, c’est-à-dire qu’elle résulte d’une construction réfléchie d’un verbe se conjuguant avec l’auxiliaire avoir.
— Ils ont cru que ces choses étaient permises
— Ils ont cru cela
— Ils ont cru ces choses permises
— Ils ont cru tout permis (pour eux)
Le verbe « croire » a donc un COD, qui est la proposition complétive « que ces choses étaient permises ». Dans la construction sans subordonnée, on peut dire que « croire » est un verbe attributif, que le COD est « tout », et que l’attribut du COD est « permis ».
Mais en tout cas, il y a un COD.

On voit donc que, le COD étant derrière, il ne peut pas être devant, comme par exemple dans « ils se sont crus autorisés à tout ».
[En réalité, si dans cette phrase on accorde souvent, il est également possible de comprendre qu’ils ne se sont pas vraiment crus, mais qu’ils ont cru qu’ils étaient autorisés, et que le COD de croire n’est pas « se » mis pour « eux-mêmes » mais la proposition entière, ce qui n’entraîne pas d’accord, et permet « ils se sont cru autorisés à tout », comme dans une construction non pronominale où on a le choix entre « des personnes qu’on avait crues malades » et « des personnes qu’on avait cru malades ».]
Mais nous ne sommes pas dans cette situation.

Donc, le pronom « se » n’est pas COD car le COD est derrière. Mais peut-être, du fait que cette expression « se croire tout permis » ne s’utilise que réflexivement (elle n’est pas vraiment une déclinaison de « ils m’ont cru tout permis », « je vous ai cru tout permis »…), faudrait-il la rapprocher des verbes obligatoirement pronominaux et accorder le participe passé avec le sujet ? Non.
D’une part parce que même si « ils lui ont cru tout permis » ne se dit pas, cela reste concevable et analysable syntaxiquement, et le pronom est facile à catégoriser :
— Ils ont cru que tout leur était permis : « leur » est un pronom de type COI
— Il ont cru tout permis (à eux)
— Ils se sont cru tout permis : « se » est un pronom de type COI
D’autre part parce que, par construction, il n’existe pas de verbe conjugué pronominalement permettant à la fois l’accord du participe passé avec le sujet et la présence d’un COD.