Faits :
A.
Par jugement du 12 novembre 2020, rectifié le 16 novembre 2020, le Tribunal correctionnel de l'arrondissement de Lausanne a pris acte du retrait par B._ de sa plainte déposée le 12 octobre 2019 et libéré A._ des chefs d'accusation de lésions corporelles simples, violation de domicile, tentative de violation de domicile et désagréments causés par la confrontation à un acte d'ordre sexuel, a pris acte du retrait par C._ de sa plainte déposée le 29 octobre 2019 et libéré A._ des chefs d'accusation de lésions corporelles simples, voies de fait, dommages à la propriété d'importance mineure, injure, menaces et violation de domicile, a constaté que A._ s'est rendu coupable de contrainte sexuelle, tentative de contrainte sexuelle et tentative de viol, a condamné A._ à une peine privative de liberté de 4 ans, sous déduction de 380 jours de détention déjà effectués, a constaté que A._ a subi 7 jours de détention dans des conditions de détention provisoire illicites et ordonné que 4 jours de détention soient déduits de la peine, à titre de réparation du tort moral, a ordonné en faveur de A._, en parallèle à la peine, un traitement psychiatrique et psychothérapeutique ambulatoire au sens de l'<ref-law>, afin de l'amener à gagner en intériorité, à mieux prendre conscience de son mode de fonctionnement, et de ce fait à mieux gérer les aspects délétères de sa personnalité, a renoncé à révoquer le sursis octroyé à A._ par le Ministère public de l'arrondissement de l'Est vaudois le 11 janvier 2018, a ordonné le maintien en détention de A._ pour des motifs de sûreté, a ordonné l'expulsion de A._ du territoire suisse pour une durée de 12 ans et l'inscription de cette mesure au SIS, a ordonné le maintien au dossier de certaines pièces à conviction. En outre, il a arrêté les indemnités d'office allouées au conseil juridique de C._, et aux défenseurs d'office de A._, a mis les frais de la cause, arrêtés à 35'097 fr., à la charge de A._, a dit que lorsque sa situation financière le permettra, il sera tenu de rembourser les indemnités d'office avancées par l'État de Vaud et a rejeté la requête de A._ en allocation d'une indemnité fondée sur l'<ref-law>.
B.
Par jugement du 30 avril 2021, la Cour d'appel pénale du Tribunal cantonal vaudois a partiellement admis l'appel formé par A._. Elle a libéré A._ du chef de tentative de viol et a constaté qu'il s'était rendu coupable de contrainte sexuelle et de tentative de contrainte sexuelle. Elle a confirmé le jugement attaqué pour le surplus. En outre, elle a dit que la détention subie depuis le jugement de première instance était déduite, a ordonné le maintien en détention de A._ à titre de sûreté et a statué sur les indemnités du conseil d'office et les frais de justice pour la procédure d'appel.
En substance, il en ressort les éléments suivants.
B.a. A._, au bénéfice d'un permis B, est né en 1979 au Portugal, pays dont il est ressortissant. Il a grandi au Portugal, puis est venu en Suisse, à U._, en 1990, accompagné de sa mère, pour y retrouver son père et son frère. Son père est arrivé en Suisse en 1985 et a obtenu un permis B en 1990. En 1996, alors que A._ venait de terminer sa neuvième année scolaire, il est retourné, avec ses parents, au Portugal, où il s'est marié avec D._. Le couple n'a pas eu d'enfant et a divorcé fin 2007. Concernant ses études, A._ a suivi au Portugal une formation de technicien en informatique, reconnue en Suisse comme un CFC en informatique. Une fois cette formation achevée, il a oeuvré dans différents secteurs, tels que la vente en bijouterie, le travail administratif, le recouvrement financier et enfin la vente dans le domaine des télécoms. De retour en Suisse en 2015, et après avoir travaillé comme aide-cuisinier, puis dans le cadre de divers emplois en intérim, il a effectué deux formations via le chômage, en particulier dans le domaine du nettoyage. Au moment de son interpellation, il travaillait dans le domaine précité, sous contrat de durée indéterminée, à un taux d'activité de 100%, au sein d'une entreprise. Son salaire variait entre 3'300 fr. et 3'500 fr. nets par mois, à raison d'une rémunération de 23 fr. 60 bruts de l'heure. Il a toutefois été licencié avant son arrestation avec effet au 31 octobre 2019. Le prénommé occupait alors une chambre dans la maison de connaissances éloignées, pour laquelle il payait un loyer de 600 fr. par mois, charges comprises. A._ a déclaré ne pas avoir de véhicule, se déplaçant en transports publics, à pied et en vélo. Au bénéfice d'un subside partiel, ses primes d'assurance-maladie s'élevaient à environ 200 fr. par mois. Le prénommé aurait des économies pour environ 12'000 fr. et n'aurait aucune dette.
Depuis janvier 2017, A._ est sapeur-pompier volontaire à V._. Entendu comme témoin de moralité aux débats, E._, commandant du Service de défense contre l'incendie et de Secours, à la caserne de V._, a indiqué que A._ était quelqu'un de très disponible, qui avait envie de s'investir et qui était motivé à aider la population. Le témoin a en outre déclaré que, dans l'exercice de sa fonction de sapeur-pompier, il avait donné entière satisfaction et s'était révélé digne de confiance. Le témoin a toutefois précisé que si A._ respectait les ordres de sa hiérarchie, il pouvait néanmoins se montrer un peu moins coopératif avec des collègues de même rang, sans toutefois qu'il n'y ait de problème particulier. Invité à décrire le caractère du prénommé, le témoin a décrit celui-ci comme pouvant se montrer impulsif, sans pour autant être violent, et comme un peu rigide parfois, remplissant sa mission à la lettre, même lorsque la situation concrète aurait nécessité un peu de flexibilité.
B.b. L'extrait du casier judiciaire suisse de A._ fait état de la condamnation suivante " 11.01.2018 : Ministère public de l'arrondissement de l'Est vaudois, violation des règles de la circulation routière, violation grave des règles de la circulation routière, peine pécuniaire de 180 jours-amende à 30 fr., sursis à l'exécution de la peine, délai d'épreuve de 2 ans et amende de 1'350 francs ".
B.c. En outre, par jugement du 23 février 2012, devenu définitif le 14 mars 2012, le Tribunal pénal de W._, au Portugal, a condamné A._ pour crime de violences conjugales, infraction contre l'intégrité corporelle qualifiée et dommages à la propriété, à une peine privative de liberté de 4 ans et 6 mois avec sursis complet, le délai d'épreuve étant de même durée que la peine.
B.d. Depuis la région de X_, le 12 octobre 2019, dans la matinée, A._ a pris contact téléphoniquement avec B._, travailleuse du sexe dont il avait trouvé les coordonnées sur Internet, pour convenir d'une relation sexuelle tarifée. Il a demandé à cette dernière de l'accueillir nue à son arrivée. Elle a toutefois refusé, en indiquant qu'elle recevait toujours en peignoir, soutien-gorge et slip et qu'elle se déshabillait une fois le prix payé. Ils ont ensuite convenu d'un rendez-vous à 18h00 pour une durée d'une heure au prix de 300 francs.
Ce même jour, vers 18h00, A._ s'est présenté à l'appartement de B._. Cette dernière, qui était vêtue d'un peignoir, d'une culotte et d'un soutien-gorge, l'a laissé entrer. Une fois à l'intérieur de l'appartement, le prénommé a immédiatement demandé à B._ pourquoi elle n'était pas nue, tout en précisant avoir avec lui l'argent convenu pour la prestation. Elle lui a répondu qu'il devait payer le prix convenu pour sa prestation avant qu'il puisse la voir dévêtue. A._ a alors ouvert le peignoir de B._ avec sa main droite et lui a touché les seins. Celle-ci a réagi en le repoussant et en lui disant « je ne veux pas que tu me touches ». Il a toutefois à nouveau touché ses seins. Elle l'a alors repoussé en lui demandant de quitter les lieux et en ouvrant la porte palière. A._, qui se trouvait sur le palier, l'a poussée contre un mur et lui a donné une forte claque sur la joue gauche. Elle a tenté de fermer la porte derrière lui, mais ce dernier a mis son pied entre la porte et le chambranle. Puis, furieux, il lui a saisi le sein gauche et l'a serré très fort dans le but notamment de satisfaire ses pulsions sexuelles. B._, qui était porteuse de prothèses mammaires, a réagi en tentant de fermer la porte avec la main droite et en repoussant le visage du prévenu avec sa main gauche, en lui mettant ses doigts dans les yeux. Elle est ainsi parvenue à refermer la porte - qui s'est verrouillée automatiquement - derrière A._. Après avoir tenté en vain d'ouvrir la porte palière et avoir donné un coup de pied dans cette celle-ci, il a quitté les lieux.
B._ a souffert de douleurs très importantes au sein gauche. Selon le rapport du 13 octobre 2019 du Service des urgences du CHUV où cette dernière s'est rendue le 12 octobre 2019, elle présentait deux hématomes sur les quadrants supérieurs médiaux du sein gauche et une palpation douloureuse du quadrant supérieur médial. Selon le rapport du 15 octobre 2019 de l'Unité de médecine des violences, où B._ s'est rendue ce jour-là, elle présentait les lésions suivantes: au niveau du dos, en regard de l'omoplate droite, une ecchymose jaune verdâtre mesurant 5,5 x 2,5 cm; au niveau du membre supérieur gauche, à la partie postérieure du tiers inférieur du bras, deux ecchymoses, la supérieure jaune vert violacée mesurant 1,7 x 1,5 cm et l'inférieure - à 1 cm de la supérieure - plus discrète, jaune verdâtre, mesurant 1,8 x 1,3 cm; au niveau du thorax, en regard du quadrant supéro-interne du sein gauche, une ecchymose jaune brunâtre mesurant 2,5 x 1,8 cm; en regard du quadrant inféro-externe du sein gauche, une ecchymose jaune vert violacée, à grand axe oblique vers le bas et le dedans, mesurant 5,5 x 2 cm.
Le 12 octobre 2019, B._ s'est constituée partie plaignante, demandeuse au pénal et au civil. A la faveur d'une convention signée avec A._ le 2 novembre 2020, elle a retiré sa plainte, à la suite de la réception d'un montant de 4'500 fr., versé par le prénommé.
B.e. Depuis la région de X._, le 16 octobre 2019, à 22h18, A._ a pris contact téléphoniquement avec C._, travailleuse du sexe dont il avait trouvé les coordonnées sur internet, pour convenir d'une relation sexuelle tarifée. Il a demandé à cette dernière de l'accueillir nue avec des bas et lui a dit, qu'au lieu de la somme de 300 fr. pour une heure, il lui donnerait 400 fr. pour une heure. C._ a refusé le rendez-vous. Puis, le prénommé l'a à nouveau contactée les jours qui ont suivi en insistant pour qu'elle lui accorde un rendez-vous. C._ a fini par accepter en lui fixant un rendez-vous le 21 octobre 2019, à 17h00, et en disant que le prix de la prestation était de 300 francs. A._ lui a répondu qu'il lui donnerait même 400 francs.
A Y._, le 21 octobre 2019, vers 17h00 A._ s'est présenté à l'appartement de C._, qui était vêtue d'un soutien-gorge, d'un short et de chaussures à talon et qui l'a laissé entrer. Après que C._ lui a demandé de payer le prix de sa prestation, le prénommé l'a immédiatement prise par les cheveux et lui a tiré la tête contre le bas en lui disant « quand je demande quelque chose, je veux que cela se fasse » et en lui demandant pourquoi elle n'était pas nue avec des bas, comme il le lui avait demandé lors de la prise de rendez-vous. C._ a prétendu faussement ne pas être seule dans l'appartement et a ouvert la porte palière en lui demandant de partir. Celui-ci l'a giflée au visage et a refermé la porte. Il l'a ensuite saisie à la gorge, avec une main en la traitant notamment de « salope » et de « pute ». C._ a perdu l'équilibre et est tombée. Alors qu'elle se trouvait au sol, A._ lui a déchiré son soutien-gorge et son short et lui a dit qu'il allait « la baiser ». Il s'est assis à califourchon sur C._, qui était couchée sur le dos et qui lui a dit que, s'il voulait avoir une relation sexuelle avec elle, il devait la payer. Il a ouvert son pantalon en lui disant « tu vas me sucer, je veux faire du sexe », C._ l'a repoussé plusieurs fois en lui disant « non ». Après qu'ils se sont relevés, il a bloqué la prénommée contre le mur avec le poids de son corps. Il l'a alors touchée au niveau du vagin avec sa main et a introduit un doigt dans son vagin. Le prénommé ayant mis son autre main sur le visage de C._, celle-ci l'a mordu. Il a alors pris la main de C._ et l'a frappée au visage avec celle-ci. Puis, il l'a à nouveau prise par les cheveux et a rapproché sa tête de son pénis en lui demandant de le « sucer ». C._ a réagi en disant qu'elle allait lui mordre le pénis. A._ l'a alors bloquée contre le mur en la tenant fortement à la gorge avec une main et en la menaçant en lui disant « je vais te tuer ». Il s'est alors masturbé avec son autre main, avant d'éjaculer en saisissant le sein droit de C._, qui était porteuse de prothèses mammaires, et en le serrant très fort comme une éponge. Il a ensuite quitté les lieux après avoir donné une forte gifle à cette dernière. Avant qu'il parte, C._ lui a dit qu'elle allait le dénoncer et il a répliqué que c'était lui qui allait la dénoncer, dès lors qu'elle vivait illégalement en Suisse. Lors de ces faits, le prénommé a également donné des coups de poing au visage de C._ pour essayer d'obtenir ce qu'il voulait.
C._ a souffert de douleurs importantes au sein droit, qui persistaient au 29 octobre 2019. Elle s'est rendue aux urgences gynécologiques du CHUV le 25 octobre 2019 et à l'Unité de sénologie du Service de gynécologie du CHUV les 28 octobre et 18 novembre 2019. Le 31 octobre 2019, elle a effectué une IRM mammaire qui a permis de conclure à un rehaussement intense de l'arc antérieur de deux côtes adjacentes à droite, rétro prothétiques, de nature indéterminée. Selon le colloque de radiologie qui s'est tenu le 11 novembre 2019, C._ a souffert d'une disjonction chondrocostale de nature traumatique des deuxième et troisième côtes.
Le 29 octobre 2019, C._ s'est constituée partie plaignante, demandeuse au pénal et au civil. A la faveur d'une convention, signée avec le prévenu le 29 octobre 2020, elle a retiré sa plainte, à la suite de la réception d'un montant de 2'500 fr. versé par A._.
B.f. En cours d'enquête, A._ a été soumis à une expertise psychiatrique, confiée au centre de psychiatrie forensique de Z._. Dans leur rapport du 8 avril 2020, les experts ont posé le diagnostic de personnalité paranoïaque. Les experts ont précisé qu'au moment des faits reprochés, le prévenu présentait déjà ce trouble de la personnalité paranoïaque, étant donné qu'il s'agit d'une constitution caractérologique chronique, mais que cela n'avait pas été de nature à altérer profondément les capacités cognitives de l'intéressé, lui permettant d'apprécier le caractère illicite des actes reprochés, ni d'altérer sa capacité à se déterminer d'après une appréciation préservée de l'illicéité de ses actes. Dans l'analyse du passage à l'acte et du risque de récidive, les experts ont retenu l'hypothèse selon laquelle l'exercice de la violence physique et sexuelle était, pour l'expertisé, une manière de gérer les angoisses et la frustration de ne pas trouver une relation féminine fusionnelle et idéale. S'agissant du risque de récidive d'actes de violence sexuelle, tant envers une travailleuse du sexe qu'envers une éventuelle nouvelle partenaire amoureuse, il avait été qualifié de moyen à élevé: moyen selon l'échelle actuarielle d'évaluation des risques de récidive sexuelle violente SORAG, mais élevé du point de vue clinique, compte tenu du diagnostic psychiatrique de l'intéressé et surtout de son mode de fonctionnement. A cet égard, les experts ont en effet précisé que la forme active, quasi obsessionnelle, que paraissait avoir prise la quête de rendez-vous avec des prostituées était particulièrement inquiétante. S'agissant d'une éventuelle mesure à prendre en faveur du prévenu, les experts ont indiqué qu'un traitement psychiatrique et psychothérapeutique pouvaient permettre un assouplissement des traits de caractère pathologiques du prévenu, afin de l'aider à trouver des alternatives au passage à l'acte violent et sexuel, de façon à réduire le risque de récidive. Bien que relevant l'ambivalence du prévenu quant à la mise en place d'un suivi psychiatrique et psychothérapeutique ambulatoire, les experts ont à ce stade estimé que ce type de traitement conservait des chances de succès auprès d'un thérapeute spécialisé dans la prise en charge de ce type de problématiques. S'agissant de l'application de ce traitement, les experts ont indiqué que celui-ci pouvait se dérouler conjointement à l'exécution d'une peine privative de liberté. En date du 29 mai 2020, les experts, amenés à donner des précisions sur le type de traitement qu'il s'agissait de mettre en oeuvre, ont expliqué que le traitement était psychiatrique (prescription médicamenteuse possible) et surtout psychothérapeutique, afin d'amener le prénommé à gagner en intériorité, à mieux prendre conscience de son mode de fonctionnement, et de ce fait à mieux gérer les aspects délétères de sa personnalité.
C.
A._ forme un recours en matière pénale au Tribunal fédéral contre le jugement du 30 avril 2021. Il conclut avec suite de frais et dépens, principalement, à sa réforme en ce qu'il est libéré de toute infraction et que sa libération immédiate est ordonnée. Il conclut également à la constatation qu'il a subi 7 jours de détention dans des conditions de détention provisoire illicite, à la restitution de son téléphone portable séquestré et que les frais de la cause et indemnités allouées aux conseils d'office sont mis a la charge de l'État. Une indemnité fondée sur l'<ref-law>, dont le montant est fixé à dire de justice, lui est allouée et les frais d'appel, par 8'116 fr. 50, y compris l'indemnité allouée à son défenseur d'office, sont laissés à la charge de l'État.
Subsidiairement, il conclut à ce que le jugement du 30 avril 2021 est réformé en ce qu'il est condamné à une peine privative de liberté de 3 ans, sous déduction de 380 jours de détention déjà effectués et qu'il est renoncé à ordonner l'expulsion de A._ du territoire suisse. Les frais de justice et les indemnités allouées aux conseils d'office sont mis à la charge de l'État. Une indemnité fondée sur l'<ref-law>, dont le montant est fixé à dire de justice, lui est allouée et les frais d'appel, par 8'116 fr. 50, y compris l'indemnité allouée au défenseur d'office, sont laissés à la charge de l'État.
Encore plus subsidiairement, il conclut à ce que le jugement du 30 avril 2021 est annulé et la cause renvoyée à la cour cantonale pour nouvelle instruction et nouveau jugement dans le sens des considérants.
Il sollicite par ailleurs l'assistance judiciaire et la désignation de Me David Parisod en qualité de défenseur d'office.

Considérant en droit :
1.
Le recourant fait grief à la cour cantonale d'avoir apprécié les preuves et établi les faits de manière arbitraire et d'avoir violé le principe de la présomption d'innocence.
1.1. Le Tribunal fédéral n'est pas une autorité d'appel, auprès de laquelle les faits pourraient être rediscutés librement. Il est lié par les constatations de fait de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, à savoir, pour l'essentiel, de façon arbitraire au sens de l'art. 9 Cst. Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable et cela non seulement dans sa motivation mais aussi dans son résultat (<ref-ruling> consid. 1.3.1; <ref-ruling> consid. 1.1; <ref-ruling> consid. 1.1; sur la notion d'arbitraire voir <ref-ruling> consid. 4.1.2 et les arrêts cités). Le Tribunal fédéral n'entre en matière sur les moyens fondés sur la violation de droits fondamentaux, dont l'interdiction de l'arbitraire, que s'ils ont été invoqués et motivés de manière précise (<ref-law>); les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 4.1.2 et les arrêts cités).
La présomption d'innocence, garantie par les <ref-law>, 32 al. 1 Cst., 14 par. 2 Pacte ONU II et 6 par. 2 CEDH, ainsi que son corollaire, le principe " in dubio pro reo ", concernent tant le fardeau de la preuve que l'appréciation des preuves au sens large. En tant que règle sur le fardeau de la preuve, elle signifie, au stade du jugement, que le fardeau de la preuve incombe à l'accusation et que le doute doit profiter au prévenu. Comme règle d'appréciation des preuves, la présomption d'innocence signifie que le juge ne doit pas se déclarer convaincu de l'existence d'un fait défavorable à l'accusé si, d'un point de vue objectif, il existe des doutes quant à l'existence de ce fait. Il importe peu qu'il subsiste des doutes seulement abstraits et théoriques, qui sont toujours possibles, une certitude absolue ne pouvant être exigée. Il doit s'agir de doutes sérieux et irréductibles, c'est-à-dire de doutes qui s'imposent à l'esprit en fonction de la situation objective. Lorsque l'appréciation des preuves et la constatation des faits sont critiquées en référence au principe " in dubio pro reo ", celui-ci n'a pas de portée plus large que l'interdiction de l'arbitraire (<ref-ruling> consid. 1.3.1; <ref-ruling> consid. 1.1).
Les déclarations de la victime constituent un élément de preuve. Le juge doit, dans l'évaluation globale de l'ensemble des éléments probatoires rassemblés au dossier, les apprécier librement (arrêts 6B_644/2021 du 6 décembre 2021 consid. 1.1; 6B_177/2021 du 8 novembre 2021 consid. 1.1; 6B_330/2021 du 15 septembre 2021 consid. 2.3), sous réserve des cas particuliers où une expertise de la crédibilité des déclarations de la victime s'impose (<ref-ruling> consid. 2.4; arrêts 6B_330/2021 précité consid. 2.3; 6B_976/2020 du 3 décembre 2020 consid. 1.2). Les cas de " déclarations contre déclarations ", dans lesquels les déclarations de la victime en tant que principal élément à charge et les déclarations contradictoires de la personne accusée s'opposent, ne doivent pas nécessairement, sur la base du principe " in dubio pro reo ", conduire à un acquittement. L'appréciation définitive des déclarations des participants incombe au tribunal du fond (<ref-ruling> consid. 3.3; arrêts 6B_644/2021 précité consid. 1.1; 6B_177/2021 précité consid. 1.1; 6B_330/2021 précité consid. 2.3).
1.2. Le recourant soutient que la cour cantonale aurait arbitrairement retenu, sur la base du jugement du 23 février 2012 rendu par le Tribunal pénal de W._ au Portugal, qu'il avait été condamné pour des violences sexuelles envers sa compagne de l'époque. Elle aurait également omis volontairement de retranscrire intégralement ce jugement, soit notamment en écartant un chapitre relatif aux " faits non prouvés ", dans lequel figureraient les allégations relatives aux relations sexuelles forcées. La cour cantonale aurait également omis de relever que le jugement portugais n'avait pas été traduit dans son entier par le Ministère public et n'aurait pas remédié à ce défaut. Ainsi, selon le recourant, des faits importants influençant la cause auraient été omis, notamment qu'il aurait admis tous les faits qui lui étaient reprochés, à l'exception des rapports sexuels forcés, et qu'il aurait souhaité intégrer un programme de soutien proposé par les services de réinsertion sociale pour les auteurs de violences domestiques.
En l'espèce, il ressort du jugement portugais - qui a été retranscrit partiellement par la cour cantonale - que le recourant avait été condamné, conformément au droit pénal portugais pour crime de violences conjugales, infraction contre l'intégrité corporelle qualifiée et dommages à la propriété. Selon les faits retenus par la justice portugaise, le recourant, en profitant de l'état de peur constante qu'il avait provoqué chez la victime, l'avait notamment amenée, à diverses occasions, à supporter la pratique de relations sexuelles, bien que telle n'était pas sa volonté, la transformant ainsi en un simple objet de ses propres passions et désirs physiques. Son but était d'atteindre à la liberté d'auto-détermination sexuelle de la victime (cf. jugement attaqué, p. 12). Dès lors, on comprend que l'infraction de " crime de violences conjugales " comporte notamment un volet relatif à l'intégrité sexuelle. La cour cantonale pouvait ainsi retenir sans arbitraire que le recourant avait déjà fait l'objet d'une condamnation au Portugal en 2012 pour de nombreuses violences psychiques, physiques et sexuelles dans le cadre de sa relation avec son ex-compagne. Contrairement à ce que prétend le recourant, il était sans importance de relever qu'il n'avait pas été condamné pour d'autres infractions sexuelles. Il était également indifférent de savoir si, dans la version intégrale du jugement portugais, parmi les " faits non prouvés ", figureraient certains épisodes de violences sexuelles. En effet, le fait que certains des épisodes de violences sexuelles n'avaient pas été prouvés (cf. pièce 65, titre 2.2; <ref-law>), ne change rien dans la mesure où la justice portugaise avait retenu qu'il avait, à diverses occasions, fait supporter la pratique de relations sexuelles contre la volonté de son ex-compagne. Partant, la cour cantonale pouvait retenir sans arbitraire qu'il avait porté atteinte à l'intégrité sexuelle de cette dernière. En outre, lorsque le recourant prétend que la cour cantonale aurait arbitrairement omis qu'il avait nié avoir eu des rapports sexuels forcés avec son ancienne compagne et qu'il souhaitait intégrer un programme pour les auteurs de violences domestiques, il ne démontre pas en quoi - pour autant que ces éléments soient avérés - la décision serait arbitraire dans son résultat.
1.3. Le recourant prétend que les déclarations des deux victimes auraient été arbitrairement tenues pour crédibles et conteste les faits retenus par la cour cantonale. Il invoque une violation du principe " in dubio pro reo ".
1.3.1. La cour cantonale a retenu que les déclarations de C._ étaient claires, détaillées, constantes et crédibles. Après avoir déposé sa plainte, le même jour, soit le 29 octobre 2019, elle avait appelé l'inspecteur de police pour compléter sa plainte, précisant que le recourant l'avait menacée de mort à plusieurs reprises. Lors de sa seconde audition, elle ne s'était contredite sur aucun élément, mais avait en revanche complété ses déclarations ensuite des questions posées par le procureur. La réaction de C._ lors d'un nouveau rendez-vous avec le recourant renforçait sa crédibilité. Ce jour-là, ni le recourant, ni la victime ne savaient qu'ils avaient rendez-vous ensemble. C._ avait utilisé un autre profil et le recourant un autre numéro de téléphone. Lorsqu'elle l'a reconnu, elle a eu peur et ne lui a pas ouvert. Le recourant avait varié dans ses explications quant aux détails des événements au fur et à mesure des différents éléments qui lui étaient présentés et sa version de gifles " accidentelles " était absurde.
S'agissant de B._, la cour cantonale a retenu que sa version des faits devait être préférée à celle du recourant. Ses déclarations étaient claires, constantes, détaillées et crédibles. B._ avait immédiatement déposé plainte. Sa plainte déposée auprès de Police secours était lacunaire, de sorte que la victime avait été entendue avec la présence d'un interprète pour plus de précisions. Les deux dépositions n'étaient pas divergentes, la victime avait uniquement complété ses déclarations.
S'agissant des deux victimes, la cour cantonale a retenu que leurs déclarations étaient également attestées par les constatations médicales suite aux agressions. La cour cantonale a également retenu que l'analyse des messages téléphoniques avec différentes prostituées attestait que le recourant avait des exigences précises ainsi qu'une attitude impulsive et directive. Le recourant avait été condamné au Portugal pour de nombreux actes d'agressions verbale, physique et sexuelle, en particulier à l'encontre de sa compagne de l'époque, ce qui démontrait qu'il était capable de violence. En outre, les deux victimes n'avaient aucune raison de mettre en cause le recourant. Elles ne le connaissaient pas et ne l'avaient jamais rencontré auparavant. Le recourant avait été identifié par le numéro de téléphone avec lequel il avait pris rendez-vous. De plus, les deux femmes avaient dénoncé des faits semblables, alors qu'elles ne se connaissaient pas. La cour cantonale a également relevé qu'il y avait de nombreux points communs entre les deux cas dénoncés. Ainsi, à chaque fois, le recourant avait demandé aux victimes d'emblée et sans les avoir payées qu'elles se dénudent, avait refusé de partir, avait serré fortement les seins des victimes et leur avait asséné une gifle.
1.3.2. Le recourant prétend que la cour cantonale se serait fondée à tort sur sa condamnation au Portugal pour retenir que les déclarations des deux victimes étaient crédibles. Or, la cour cantonale a retenu, sans que le recourant n'en démontre l'arbitraire (cf. consid. 1.2), qu'il avait agressé verbalement, physiquement et sexuellement son ancienne compagne au Portugal. Ainsi, la cour cantonale pouvait - à juste titre - retenir qu'il était capable de violence et que cet élément allait dans le sens des déclarations des victimes.
1.3.3. Le recourant soutient que la cour cantonale ne pouvait retirer un quelconque gage de crédibilité des victimes sur la base de quelques éléments communs qui ressortaient de leurs déclarations, car il n'avait jamais nié avoir rencontré les deux prostituées. On ne distingue pas la logique de cet argument. Il n'était pas question de savoir si le recourant avait admis avoir vu les deux travailleuses du sexe, mais bien de déterminer si la cour cantonale pouvait retenir, sans arbitraire, que les similitudes entre les agressions formaient un indice en faveur de la crédibilité des récits des victimes. Il ressort du jugement attaqué que les faits dénoncés par les deux victimes comportent de nombreux points communs, alors même que les victimes ne se connaissaient pas. Les similitudes sont frappantes, le recourant ayant pris rendez-vous avec les deux travailleuses du sexe en spécifiant, à chaque fois, vouloir qu'elles soient nues à son arrivée. Dans les deux cas, il a commencé à les agresser dès son arrivée en leur reprochant de n'avoir pas obéi à ses consignes. La manière dont il a saisi et blessé un sein à chacune des victimes est également significative. La cour cantonale pouvait, sans arbitraire, retenir que ces similitudes donnaient du crédit aux récits des victimes.
1.4. Le recourant soutient que la cour cantonale aurait arbitrairement retenu que les déclarations de C._ étaient crédibles alors qu'elles auraient été incohérentes. En tant que l'argumentation du recourant consiste uniquement à opposer sa propre appréciation des moyens de preuve et sa version des faits à celles de la cour cantonale, elle est purement appellatoire. Il en va notamment ainsi lorsqu'il prétend que ce n'était pas par peur qu'elle n'avait pas souhaité initialement porter plainte et que ce n'était que sur insistance de ses amis qu'elle aurait changé d'avis. Il en va de même lorsqu'il soutient que la victime aurait aggravé les faits dénoncés lors de la deuxième audition et que la cour cantonale aurait dû analyser la pertinence du récit, car il était surprenant que des faits si importants n'apparaissent que dans un second temps. Sur ce point, la cour cantonale a expliqué qu'après avoir déposé sa plainte, le jour-même, la victime avait appelé l'inspecteur de police pour compléter sa plainte, précisant que le recourant l'avait menacée de mort à plusieurs reprises. Lors de la deuxième audition, la victime avait complété ses déclarations sur questions du procureur sans se contredire. Au regard de ce contexte, la cour cantonale a retenu, à raison, que les précisions apportées par la victime ne remettaient aucunement en cause sa crédibilité.
Au surplus, le recourant prétend qu'il ressortirait des déclarations de C._ qu'elle avait reconnu le recourant lorsqu'il avait fixé un nouveau rendez-vous et qu'elle avait sciemment accepté de se représenter devant lui. Ainsi, son attitude mettrait en doute sa crédibilité. En l'espèce, la cour cantonale a retenu qu'elle ne savait pas qu'il s'agissait du recourant, car ce dernier avait utilisé un autre numéro de téléphone. Il ressort de l'audition de la victime qu'elle ne savait pas qu'il s'agissait du recourant, mais qu'elle avait un doute sur l'identité du client, raison pour laquelle, par précaution, elle était descendue vérifier à la porte de son immeuble, en laissant la porte de son appartement ouverte et en sachant que la porte de son immeuble ne pouvait pas s'ouvrir de l'extérieur. Après avoir constaté qu'il s'agissait du recourant, elle est remontée sans lui ouvrir, elle n'avait pas réussi à dormir durant deux nuits et avait peur de sortir de chez elle (cf. audition du 25 novembre 2019, p. 3; <ref-law>). Au regard de ce qui précède, la cour cantonale pouvait sans arbitraire considérer que la réaction de la victime lors du nouveau rendez-vous avec le recourant renforçait sa crédibilité.
1.5. Le recourant soutient que la cour cantonale aurait arbitrairement retenu que les déclarations de B._ étaient crédibles alors qu'elles auraient été incohérentes. Il prétend notamment que ses déclarations seraient contradictoires s'agissant de la description du rendez-vous qu'il avait souhaité et qu'elle aurait aggravé ses accusations lors de sa seconde audition. Dans la mesure où elle s'écarte des éléments retenus par la cour cantonale sans démontrer que ceux-ci auraient été établis de manière arbitraire, son exposé est appellatoire, partant irrecevable.
1.6. Le recourant soutient que la cour cantonale se serait arbitrairement fondée sur les lésions constatées médicalement chez les deux victimes pour retenir qu'il avait attenté à leur intégrité sexuelle. Selon lui, il était arbitraire de considérer qu'un comportement violent impliquerait automatiquement la possibilité de commettre des agissements contre l'intégrité sexuelle. En l'espèce, au regard des constatations médicales relatives notamment aux lésions sur les seins des victimes, la cour cantonale pouvait, à juste titre, retenir que ces éléments venaient attester les dires des victimes.
1.7. Vu ce qui précède, le recourant, échoue à démontrer que la cour cantonale aurait versé dans l'arbitraire (cf. art. 97 al. 1 et 105 al. 1 LTF) en retenant que les déclarations des deux victimes étaient crédibles. Partant, le grief est rejeté, dans la mesure où il est recevable. De plus, conformément à la jurisprudence (cf. supra consid. 1.1), le principe " in dubio pro reo " n'a ici pas de portée plus large que l'interdiction de l'arbitraire.
2.
Le recourant conteste sa condamnation pour contrainte sexuelle (<ref-law>) sur la personne de B._. Il reproche également à la cour cantonale d'avoir établi les faits de manière arbitraire.
2.1. Conformément à l'<ref-law>, celui qui, notamment en usant de menace ou de violence envers une personne, en exerçant sur elle des pressions d'ordre psychique ou en la mettant hors d'état de résister l'aura contrainte à subir un acte analogue à l'acte sexuel ou un autre acte d'ordre sexuel, sera puni d'une peine privative de liberté de dix ans au plus ou d'une peine pécuniaire.
2.2. Constitue un acte d'ordre sexuel au sens de cette disposition une activité corporelle sur soi-même ou sur autrui qui tend à l'excitation ou à la jouissance sexuelle de l'un des participants au moins (arrêts 6B_249/2021 du 13 septembre 2021 consid. 3.5.3; 6B_1414/2020 du 11 août 2021 consid. 2.2; 6B_231/2020 du 25 mai 2020 consid. 3.1). Selon la jurisprudence, il faut d'abord distinguer les actes n'ayant aucune apparence sexuelle, qui ne tombent pas sous le coup de la loi, des actes clairement connotés sexuellement du point de vue de l'observateur neutre, qui remplissent toujours la condition objective de l'infraction, indépendamment des mobiles de l'auteur. Dans les cas équivoques, il convient de tenir compte de l'ensemble des éléments d'espèce (cf. <ref-ruling> consid. 3b et les références citées).
Un baiser sur la bouche ou une tape sur les fesses ne sont en principe pas des actes d'ordre sexuel tombant sous le coup de l'<ref-law>. En revanche, un baiser lingual ou des baisers insistants sur la bouche revêtent indiscutablement un caractère sexuel (<ref-ruling> consid. 3b; arrêts 6B_249/2021 précité consid. 3.5.3; 6B_44/2020 du 16 septembre 2020 consid. 5.1). Il en va de même d'une caresse insistante du sexe, des fesses ou des seins, même par-dessus les habits (arrêts 6B_249/2021 précité consid. 3.5.3; 6B_1097/2019 du 11 novembre 2019 consid. 2.1; 6B_732/2018 du 18 septembre 2018 consid. 3.1.3).
Sur le plan subjectif, l'auteur doit agir intentionnellement, ce qui implique qu'il doit être conscient du caractère sexuel de son comportement, mais ses motifs ne sont pas déterminants, de sorte qu'il importe peu que l'acte tende ou non à l'excitation ou à la jouissance sexuelle (arrêts 6B_231/2020 précité consid. 3.1; 6B_299/2018 du 4 juillet 2018 consid. 2.1.1; 6B_180/2018 du 12 juin 2018 consid. 3.1 et les arrêts cités). Le dol éventuel suffit (arrêt 6B_1306/2017 du 17 mai 2018 consid. 2.1.2).
2.3. En substance la cour cantonale a condamné le recourant pour contrainte sexuelle à l'encontre de B._ (en lien avec les faits décrits sous lettre B.d). La cour cantonale a estimé que les attouchements sur la poitrine de la victime, à trois reprises et d'une manière extrêmement brutale pour la dernière fois, n'étaient absolument pas des actes neutres, mais au contraire connotés sexuellement. L'absence de consentement était évidente.
2.4. Le recourant soutient que la cour cantonale aurait retenu arbitrairement qu'il avait serré le sein gauche de B._ dans le but notamment de satisfaire ses pulsions sexuelles. Il argue qu'il ne ressortirait pas des déclarations de la victime qu'il aurait été excité sexuellement et que la cour cantonale aurait omis de retenir que la victime avait déclaré qu'il était furieux. Contrairement à ce que prétend le recourant, la cour cantonale a bien retenu qu'il était furieux lorsqu'il avait saisi le sein de sa victime (cf. jugement attaqué, p. 14). Elle a retenu, en outre, que ce geste avait notamment pour but de satisfaire ses pulsions sexuelles. A cet égard, on ne voit pas en quoi le sentiment de fureur et la satisfaction de pulsions sexuelles seraient antinomiques. En outre, il ressort du jugement attaqué qu'à son arrivée dans l'appartement de la travailleuse du sexe, le recourant lui a immédiatement demandé pourquoi elle n'était pas nue, lui a ouvert le peignoir avec la main droite et lui a touché les seins. B._ l'avait repoussé en lui disant qu'elle ne voulait pas être touchée et le recourant lui a, à nouveau, touché les seins. Elle l'a alors repoussé et lui a demandé de quitter les lieux. Il l'a alors poussée contre un mur, lui a donné une forte claque sur la joue gauche, puis lui a saisi le sein gauche qu'il a serré très fort. Au regard du déroulement des événements, la cour cantonale pouvait se convaincre, sans verser dans l'arbitraire, que le recourant poursuivait notamment le but de satisfaire ses pulsions sexuelles.
2.5. Le recourant conteste sa condamnation pour contrainte sexuelle au motif qu'il n'y aurait pas eu d'acte d'ordre sexuel. Il soutient que le fait de serrer le sein d'une femme, au point de le blesser, constituerait tout au plus des voies de fait, subsidiairement des lésions corporelles simples. L'argument du recourant ne peut pas être suivi, car le fait d'avoir blessé le sein de sa victime ne permet en rien de dénier le caractère sexuel objectif et indiscutable de l'acte consistant à saisir, d'une pleine main, un sein et de le serrer. Pour le surplus, le recourant ne conteste pas la réalisation des autres éléments constitutifs de l'infraction.
3.
Le recourant se plaint de la peine qui lui a été infligée. Il semble également reprocher un défaut de motivation.
3.1. Selon l'<ref-law>, le juge fixe la peine d'après la culpabilité de l'auteur. Il prend en considération les antécédents et la situation personnelle de ce dernier ainsi que l'effet de la peine sur son avenir (al. 1). La culpabilité est déterminée par la gravité de la lésion ou de la mise en danger du bien juridique concerné, par le caractère répréhensible de l'acte, par les motivations et les buts de l'auteur et par la mesure dans laquelle celui-ci aurait pu éviter la mise en danger ou la lésion, compte tenu de sa situation personnelle et des circonstances extérieures (al. 2). La culpabilité doit être évaluée en fonction de tous les éléments objectifs pertinents, qui ont trait à l'acte lui-même, à savoir notamment la gravité de la lésion, le caractère répréhensible de l'acte et son mode d'exécution. Du point de vue subjectif, sont pris en compte l'intensité de la volonté délictuelle ainsi que les motivations et les buts de l'auteur. A ces composantes de la culpabilité, il faut ajouter les facteurs liés à l'auteur lui-même, à savoir les antécédents (judiciaires et non judiciaires), la réputation, la situation personnelle (état de santé, âge, obligations familiales, situation professionnelle, risque de récidive, etc.), la vulnérabilité face à la peine, de même que le comportement après l'acte et au cours de la procédure pénale (<ref-ruling> consid. 6 et les références citées).
Le juge dispose d'un large pouvoir d'appréciation dans la fixation de la peine. Le Tribunal fédéral n'intervient que lorsque l'autorité cantonale a fixé une peine en dehors du cadre légal, si elle s'est fondée sur des critères étrangers à l'<ref-law>, si des éléments d'appréciation importants n'ont pas été pris en compte ou, enfin, si la peine prononcée est exagérément sévère ou clémente au point de constituer un abus du pouvoir d'appréciation (<ref-ruling> consid. 1.2; <ref-ruling> consid. 5.6). L'exercice de ce contrôle suppose que le juge exprime, dans sa décision, les éléments essentiels relatifs à l'acte ou à l'auteur qu'il prend en compte, de manière à ce que l'on puisse constater que tous les aspects pertinents ont été pris en considération et comment ils ont été appréciés, que ce soit dans un sens aggravant ou atténuant (<ref-law>; <ref-ruling> consid. 1.2). Le juge peut passer sous silence les éléments qui, sans abus du pouvoir d'appréciation, lui apparaissent non pertinents ou d'une importance mineure. La motivation doit justifier la peine prononcée, en permettant de suivre le raisonnement adopté. Un recours ne saurait toutefois être admis simplement pour améliorer ou compléter un considérant lorsque la décision rendue apparaît conforme au droit (<ref-ruling> consid. 1.2; <ref-ruling> consid. 5.6).
3.2. La cour cantonale a exposé que les faits retenus à la charge du recourant, qui répond d'un concours d'infraction, étaient extrêmement graves et sa culpabilité très lourde. Il avait démontré son mépris absolu pour l'intégrité sexuelle d'autrui, ne reculant devant aucune bassesse pour assouvir ses besoins sexuels de domination. Les victimes qui, par leur métier, étaient pourtant habituées à gérer des situations délicates, avaient été traumatisées par les actes du recourant, au point qu'elles avaient demandé à ce que leur adresse reste confidentielle. Ce n'était pas la première fois que le recourant s'attaquait à des femmes, puisqu'il avait déjà fait l'objet d'une condamnation au Portugal en 2012 pour de nombreuses violences psychiques, physiques et sexuelles dans le cadre de sa relation avec sa compagne de l'époque. Malgré cette précédente condamnation à une peine privative de liberté de 4 ans et demi, certes avec sursis complet, le recourant n'avait pas été dissuadé de commettre à nouveau des infractions contre l'intégrité sexuelle. Bien plus, il persistait à minimiser, voire à nier les faits, tenant tour à tour, pour améliorer sa situation, de rejeter la faute sur les victimes, de ternir leur crédibilité, puis de s'en prendre au travail des enquêteurs, et de mentir quant à la teneur du jugement portugais. Sa persistance à nier certaines évidences du dossier, sans la moindre considération pour ses victimes, démontrait qu'il n'avait manifestement pas pris conscience de la gravité de ses actes ni de leurs conséquences. Enfin, la cour cantonale n'a trouvé guère d'éléments à décharge, si ce n'était les excuses que le recourant avait présentées aux victimes dans les conventions signées avec celles-ci, déclarant souhaiter reconnaître, par ce biais, les souffrances causées, et le fait qu'il leur avait versé des montants non négligeables, même si ces excuses apparaissaient de pur apparat.
La cour cantonale a estimé que, pour des motifs de prévention spéciale, seule une peine privative de liberté conséquente pouvait être prononcée en l'espèce. Le recourant devait recevoir un message dissuasif pour que l'on puisse espérer qu'il parvienne à se contenir. La cour cantonale a estimé que les actes les plus graves étaient les actes de contrainte sexuelle commis à l'encontre de C._, qui devaient être sanctionnés par une peine privative de liberté de 2 ans. Par l'effet du concours, cette peine était augmentée d'une année pour les actes de contrainte sexuelle commis à l'encontre de B._. La peine étant encore augmentée d'un an pour les actes de tentative de contrainte sexuelle commis à l'encontre de C._. La cour cantonale a précisé que l'abandon du chef de prévention de tentative de viol ne conduisait pas à une réduction de la peine en raison des actes très graves du recourant qui étaient les mêmes que ceux retenus en première instance.
3.3. Le recourant soutient que la cour cantonale se serait fondée sur des éléments erronés pour apprécier sa culpabilité, à savoir qu'il aurait fait l'objet d'une condamnation en lien avec des violences sexuelles et qu'il aurait menti s'agissant de la teneur du jugement portugais. Compte tenu des faits établis, sans que l'arbitraire n'en soit démontré (cf. supra consid. 1.2), la cour cantonale pouvait retenir ces éléments.
3.4. Le recourant se prévaut d'une violation de l'<ref-law>. Il soutient que la cour cantonale, qui l'avait libéré du chef de prévention de tentative de viol, aurait, à tort, refusé de réduire la peine par rapport à celle infligée en première instance. Selon lui, compte tenu du fait que sa volonté de forcer l'acte sexuel avait été écartée, sa culpabilité devait en être a fortiori diminuée. Il soulève également que la sanction pour l'infraction de viol est plus sévère que celle de l'<ref-law>. Le recourant perd de vue que la cour cantonale disposait d'un plein pouvoir d'examen en fait et en droit (cf. art. 398 al. 2 et 408 CPP) sur les points attaqués (cf. <ref-ruling> consid. 1.3.3; arrêts 6B_757/2020 du 4 novembre 2020 consid. 3.3.2; 6B_249/2016 du 19 janvier 2017 consid. 1.4.1), aussi pour ce qui concerne les pures questions d'appréciation comme la fixation de la peine (cf. arrêts 6B_316/2021 du 30 septembre 2021 consid. 1.3.1; 6B_798/2017 du 14 mars 2018 consid. 2.4; 6B_812/2015 du 16 juin 2016 consid. 2.1 et les références citées). Ainsi, la cour cantonale a rendu un nouveau jugement dans lequel il lui revenait de fixer librement la peine. Dès lors, le reproche du recourant est sans fondement.
Pour le surplus, le recourant semble reprocher à la cour cantonale un défaut de motivation. Il apparaît douteux que son grief, qui relève du droit d'être entendu que le recourant n'évoque même pas, soit suffisamment motivé. Quoi qu'il en soit, la motivation détaillée de la cour cantonale permet pleinement de comprendre pourquoi la peine prononcée est identique à celle de première instance malgré la libération du chef d'accusation de tentative de viol. Partant, les critiques du recourant sont rejetées dans la mesure où elles sont recevables.
3.5. Le recourant prétend que la cour cantonale aurait, en maintenant la peine fixée par l'autorité de première instance, procédé à un abus de son pouvoir d'appréciation. Il soutient que la peine ne devrait pas excéder 3 ans de peine privative de liberté.
Comme l'a relevé la cour cantonale, les actes du recourant sont extrêmement graves et sa culpabilité très lourde. Il a démontré son mépris absolu pour l'intégrité sexuelle d'autrui et les infractions retenues entrent en concours. Sa condamnation au Portugal ne l'avait pas dissuadé de commettre à nouveau des infractions contre des femmes. Il avait minimisé, voire nié les faits et n'avait pas pris conscience de la gravité de ses actes ni de leurs conséquences. Compte tenu de l'ensemble de ces circonstances, la peine privative de liberté de 4 ans qui lui a été infligée n'apparaît pas exagérément sévère au point de procéder d'un abus du large pouvoir d'appréciation dont disposait la cour cantonale.
3.6. Le recourant tente encore la comparaison avec les peines prononcées dans d'autres affaires.
Dans le contexte de la fixation de la peine, le recourant peut faire valoir une inégalité de traitement. Compte tenu toutefois des nombreux paramètres qui interviennent dans la fixation de la peine, une comparaison avec des affaires concernant d'autres accusés et des faits différents est d'emblée délicate (<ref-ruling> consid. 6.3.2). Le recourant invoque deux arrêts du Tribunal fédéral. Il s'agit à chaque fois d'affaires qui se distinguent à plus d'un titre de celle d'espèce, ce qui exclut d'emblée une comparaison.
3.7. Le recourant invoque également une réduction de peine fondée sur l'acquittement du chef d'accusation de contrainte sexuelle. Dès lors qu'il ne l'obtient pas, son argumentation est irrecevable.
4.
Le recourant critique son expulsion du territoire suisse. Il forme différentes critiques quant à l'établissement des faits.
4.1. Aux termes de l'<ref-law>, le juge expulse de Suisse l'étranger qui est condamné pour contrainte sexuelle (let. h), quelle que soit la quotité de la peine prononcée à son encontre, pour une durée de cinq à quinze ans.
En l'espèce, la cour cantonale a condamné le recourant pour les chefs de contrainte sexuelle et de tentative de contrainte sexuelle. Dans ses développements, le recourant ne conteste pas que les conditions d'une expulsion au regard de l'art. 66a al. 1 let. h CP sont remplies. Le recourant entend néanmoins se prévaloir de la clause de rigueur de l'<ref-law>.
4.2. L'<ref-law> prévoit que le juge peut exceptionnellement renoncer à une expulsion lorsque celle-ci mettrait l'étranger dans une situation personnelle grave (première condition) et que les intérêts publics à l'expulsion ne l'emportent pas sur l'intérêt privé de l'étranger à demeurer en Suisse (deuxième condition). À cet égard, il tiendra compte de la situation particulière de l'étranger qui est né ou qui a grandi en Suisse.
La clause de rigueur permet de garantir le principe de la proportionnalité (art. 5 al. 2 Cst.). Elle doit être appliquée de manière restrictive (<ref-ruling> consid. 3.4.2; <ref-ruling> consid. 3.3.1). Selon la jurisprudence du Tribunal fédéral (<ref-ruling> consid. 3.4; <ref-ruling> consid. 3.3.2), il convient de s'inspirer des critères énoncés à l'art. 31 de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201). L'art. 31 al. 1 OASA prévoit qu'une autorisation de séjour peut être octroyée dans les cas individuels d'extrême gravité. L'autorité doit tenir compte notamment de l'intégration du requérant selon les critères définis à l'art. 58a al. 1 de la loi fédérale sur les étrangers et l'intégration (LEI; RS 142.20), de la situation familiale, particulièrement de la période de scolarisation et de la durée de la scolarité des enfants, de la situation financière, de la durée de la présence en Suisse, de l'état de santé ainsi que des possibilités de réintégration dans l'État de provenance. Comme la liste de l'art. 31 al. 1 OASA n'est pas exhaustive et que l'expulsion relève du droit pénal, le juge devra également, dans l'examen du cas de rigueur, tenir compte des perspectives de réinsertion sociale du condamné (ATF <ref-ruling> consid. 3.3.2). En règle générale, il convient d'admettre l'existence d'un cas de rigueur au sens de l'<ref-law> lorsque l'expulsion constituerait, pour l'intéressé, une ingérence d'une certaine importance dans son droit au respect de sa vie privée et familiale garanti par la Constitution fédérale (art. 13 Cst.) et par le droit international, en particulier l'art. 8 CEDH (arrêts 6B_177/2021 précité consid. 3.1.1; 6B_330/2021 précité consid. 4.2.1; 6B_825/2020 du 28 octobre 2020 consid. 4.1).
4.3. Selon la jurisprudence, pour se prévaloir du droit au respect de sa vie privée au sens de l'art. 8 par. 1 CEDH, l'étranger doit établir l'existence de liens sociaux et professionnels spécialement intenses avec la Suisse, notablement supérieurs à ceux qui résultent d'une intégration ordinaire. Le Tribunal fédéral n'adopte pas une approche schématique qui consisterait à présumer, à partir d'une certaine durée de séjour en Suisse, que l'étranger y est enraciné et dispose de ce fait d'un droit de présence dans notre pays. Il procède bien plutôt à une pesée des intérêts en présence, en considérant la durée du séjour en Suisse comme un élément parmi d'autres et en n'accordant qu'un faible poids aux années passées en Suisse dans l'illégalité, en prison ou au bénéfice d'une simple tolérance (cf. <ref-ruling> consid. 4.3; arrêts 6B_990/2020 du 26 novembre 2021 consid. 3.2.2; 6B_316/2021 du 30 septembre 2021 consid. 2.3). Un séjour légal de dix années suppose en principe une bonne intégration de l'étranger (<ref-ruling> consid. 3.9).
4.4. La cour cantonale a retenu que le recourant n'avait vécu en Suisse que pendant six ans alors qu'il était enfant et n'y était revenu qu'en 2015. Son contrat de travail avait été résilié avant son arrestation et il n'avait pas de proche en Suisse, à l'exception de son frère qui avait toutefois rompu les relations. La cour cantonale a retenu que le recourant ne rencontrera vraisemblablement pas davantage de difficulté de réinsertion au Portugal qu'en Suisse. Elle a estimé qu'il ne s'exposait pas à une situation personnelle grave en cas de renvoi dans son pays d'origine, qui offre des conditions d'existence décentes. Elle a également estimé que, compte tenu de la gravité des infractions en cause, portant atteinte à des biens juridiques importants tels que l'intégrité sexuelle, du risque effectif de récidive et de ses perspectives de réinsertion au Portugal, l'intérêt public à l'éloignement du recourant l'emportait sur l'intérêt privé de celui à demeurer en Suisse. Elle a ainsi confirmé l'expulsion prononcée en première instance d'une durée de 12 ans, en l'estimant proportionnée à l'importance de la peine, ainsi qu'à l'absence de toute attache avec la Suisse.
4.4.1. Le recourant soutient que la cour cantonale aurait omis arbitrairement de nombreux éléments en faveur de son intérêt à demeurer en Suisse. A cet égard, il se contente d'affirmer qu'il aurait des amis très proches en Suisse, que son intégration en Suisse serait excellente de même que sa maîtrise de la langue française, qu'il aurait débuté un suivi psychologique en détention qu'il souhaite continuer en liberté et qu'ainsi il ne saurait être considéré comme une menace pour la sécurité publique. De plus, il soutient que, grâce à ses contacts, il sera en mesure de retrouver facilement un travail et qu'il était apprécié dans le cadre de son activité de sapeur-pompier volontaire. En tant que l'argumentation du recourant consiste uniquement à opposer sa propre version des faits à celle de la cour cantonale, ou à ajouter des faits non constatés sans démontrer, conformément aux exigences de motivation accrue (cf. <ref-law>), en quoi ceux-ci auraient fait l'objet d'une omission arbitraire, elle est purement appellatoire. Au demeurant, la cour cantonale a bien établi, se référant aux experts, qu'un traitement psychiatrique et psychothérapeutique pouvait amener le recourant à gager en intériorité et à mieux prendre conscience de son mode de fonctionnement, et de ce fait à mieux gérer les aspects délétères de sa personnalité (cf. jugement attaqué p. 18). Elle a d'ailleurs ordonné un tel traitement ambulatoire (<ref-law>). Cela étant, il n'en reste pas moins qu'il existe un risque de récidive concret en matière de crime sexuel. S'agissant du fait que le recourant parlerait le français, la cour cantonale ne dit rien sur ses compétences linguistiques, cela étant une certaine maîtrise du français ressort implicitement du fait que le recourant a vécu six ans en Suisse lorsqu'il était enfant. Quoi qu'il en soit, cet élément n'est pas propre, à lui seul, à modifier la décision dans son résultat.
Eu égard à ce qui précède, le grief d'arbitraire est infondé, dans la mesure de sa recevabilité.
4.4.2. Le recourant prétend que la cour cantonale aurait retenu à tort que les conditions d'application du cas de rigueur n'étaient pas remplies. Il invoque à cet égard l'art. 8 par. 1 CEDH.
4.4.3. S'agissant de la première condition de l'<ref-law>, comme déjà mentionné, le recourant n'a vécu en Suisse, alors qu'il était enfant, que pendant six ans et n'y est revenu qu'en 2015. Il n'a ni travail, ni proche en Suisse, à l'exception de son frère qui a toutefois rompu les relations. Il a suivi au Portugal une formation de technicien en informatique et ses perspectives de réinsertion dans ce pays ne sont pas défavorables. Dans ces conditions, la cour cantonale a retenu, à juste titre, qu'un renvoi du recourant au Portugal, ne le placerait pas dans une situation personnelle grave. En tout état de cause, l'intérêt public à l'expulsion du recourant l'emporte sur son intérêt privé à demeurer en Suisse, compte tenu de la gravité des infractions commises portant atteinte à des biens juridiques importants tels que l'intégrité sexuelle, du risque effectif de récidive et de ses perspectives de réinsertion au Portugal. L'expulsion ordonnée pour une durée de 12 ans, s'avère conforme au principe de la proportionnalité découlant des art. 5 al. 2 Cst. et 8 par. 2 CEDH. Les conditions pour l'application de l'<ref-law> n'étant pas réalisées, la cour cantonale n'a pas violé le droit fédéral en ordonnant l'expulsion du recourant.
5.
Le recourant conclut à l'octroi d'une indemnité fondée sur l'<ref-law> en lien avec l'acquittement qu'il réclame, subsidiairement avec la diminution de peine réclamée. Comme il n'obtient ni l'un ni l'autre, cette conclusion est sans objet.
6.
Le recours doit être rejeté dans la mesure où il est recevable. Comme il était dénué de chance de succès, la demande d'assistance judiciaire doit être rejetée (<ref-law>). Le recourant, qui succombe, supporte les frais judiciaires, dont le montant sera fixé en tenant compte de sa situation financière, laquelle n'apparaît pas favorable (art. 65 al. 2 et 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La requête d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1200 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 7 février 2022
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
La Présidente : Jacquemoud-Rossari
La Greffière : Meriboute