L’adjectif s’accorde avec le mot qu’il qualifie. Dans votre phrase, tous les mots sont analysables, ils ont la fonction que leur nature et leur position suggèrent, et l’adjectif est ici attribut du sujet : ils sont naturels, ils paraissent naturels, ils paraissent très naturels, il paraissent le plus naturels possible. L’adjectif est entouré ici par l’expression adverbiale « le plus … possible », mais il reste un adjectif attribut du sujet « ils », s’accordant donc au pluriel.

Et si votre question concerne la tentation qu’on a parfois de voir une expression composée d’un verbe et d’un adjectif invariable dans des locutions comme « paraître-naturel », « faire-joli », « rester-coi », comme dans une expression qu’on pourrait détacher du sujet pour mieux l’appliquer au verbe, non, cela n’existe pas, même quand c’est tentant.
– Il faut paraître naturel, et pour paraître vraiment naturels, nous devons…
– Les fleurs, il faut que ça fasse joli ; les fleurs doivent faire jolies, le plus jolies possible…
– Il faut rester coi, et, jeunes filles, merci de rester coites…

L’adjectif invariable lié à un verbe existe certes (parler fort, porter beau), mais l’adjectif ne peut pas dans ce cas être analysé comme attribut d’un autre mot. Attribut ou épithète, l’accord de l’adjectif est presque systématique, indépendamment d’une expression adverbiale pouvant apparaître dans la phrase.