L’adjectif s’accorde toujours avec le nom ou le pronom auquel il se rapporte. La construction n’importe pas.
— Je crois ces choses compatibles avec le caramel.
— Je les crois compatibles avec le caramel.
Non, vous n’avez pas du tout le choix pour l’accord de l’adjectif « compatibles ».

Pour l’accord du participe passé, certains verbes, comme le verbe « croire », offrent le choix, selon qu’on considère que :
— le COD est une proposition : croire [que ces parfums sont compatibles], auquel cas on n’accorde pas ;
— le COD est un nom suivi d’un attribut du COD : croire [ces parfums] compatibles, auquel cas on accorde.
Le sens impose la première option, mais l’usage permet de considérer dans votre phrase que « ces parfums » est COD formel de « croire » (ce qu’il n’est pourtant pas sémantiquement) ; on accorde alors avec le « COD apparent ».

Interprétation où le COD logique pour l’accord est le COD sémantique, c’est-à-dire une proposition :
— On a cru que ces parfums étaient compatibles avec…
–> on a cru ces parfums compatibles avec…
–> ces parfums qu’on a cru compatibles avec…

Interprétation où le COD logique pour l’accord est le COD syntaxique apparent, c’est-à-dire un substantif ou son pronom :
— On a cru ces parfums, comment les a-t-on crus ? quelles qualités leur a-t-on attribué ? on les a crus compatibles avec…
–> on a cru ces parfums compatibles avec…
–> ces parfums qu’on a crus compatibles avec…

C’est vous qui voyez. Pour répondre formellement à votre question, il n’y a pas de règle particulière sur l’accord du participe passé avec son COD antéposé, mais il y a deux façons d’interpréter ce qu’est un COD.