Considérant en droit:
1. Dans la mesure où le recourant invoque une violation du principe de la présomption d'innocence parce que les faits retenus à son encontre ne seraient établis par aucune preuve directe, son grief est irrecevable. En effet, la cause avait été renvoyée à l'autorité cantonale par la cour de céans pour qu'il soit à nouveau statué sur la peine. Par conséquent, seule cette question peut faire l'objet du recours.
2. Invoquant une violation de l'art. 47 CP, le recourant juge sa peine excessivement sévère et reproche aux juges cantonaux de ne pas avoir tenu compte de sa situation personnelle, ni de l'écoulement du temps.
2.1 L'art. 47 CP correspond à l'art. 63 aCP et à la jurisprudence y relative, laquelle conserve donc sa valeur (cf. arrêt 6B_472/2007 consid. 8.1). Cette jurisprudence a été rappelée dans l'<ref-ruling> consid. 6.1 et dans l'ATF 6B_771/2007 qui concerne le recourant et auxquels on peut donc se référer.
2.2 La cour cantonale a jugé que la culpabilité du recourant était importante. Elle a relevé que, pour assouvir ses pulsions sexuelles, ce dernier n'avait pas hésité à s'en prendre à une jeune fille particulièrement vulnérable et qu'il avait profité de la confiance et de la fragilité de sa victime, déjà abusée à l'âge de six ans par son grand-père, puis traumatisée à la suite d'une interruption de grossesse et confrontée à un climat de violence domestique depuis le décès de son père. Elle a constaté que le recourant avait commis, à quelques semaines d'écart, deux viols, auxquels s'ajoutait un baiser lingual donné à une autre jeune fille et a souligné la différence d'âge entre l'auteur et ses victimes. La cour cantonale a également retenu que le recourant n'avait eu de cesse de nier les faits, qu'il n'avait jamais exprimé le moindre regret, qu'il avait même tenté de charger une des victimes pour se soustraire à une condamnation, ce qui était révélateur de son manque de scrupules, et qu'il avait eu des déclarations éloquentes quant à son mépris pour sa victime. Elle a aussi considéré que la responsabilité de l'intéressé était entière et qu'il ne bénéficiait d'aucune circonstance atténuante, l'écoulement du temps n'étant pas suffisant pour constituer la circonstance de l'art. 48 let. e CP. Elle a enfin tenu compte du concours d'infractions.
Au vu de la culpabilité du recourant, telle qu'elle résulte des éléments précités, ainsi que de la sanction encourue pour les infractions commises, la peine complémentaire qui lui a été infligée, à savoir quarante-six mois et sept jours de privation de liberté, ne peut être qualifiée d'excessive au point qu'elle doive être considérée comme procédant d'un abus du pouvoir d'appréciation. Pour le reste, contrairement à ce que prétend le recourant, l'écoulement du temps n'a pas été ignoré, mais n'a pas été retenu, à juste titre (cf. <ref-ruling> consid. 6.2), comme circonstance atténuante au sens de l'art. 48 let. e CP. Quant à la situation personnelle du recourant, elle a été rappelée et, sur la base des faits constatés dont ne peut s'écarter l'intéressé, elle n'apparaît pas si exceptionnelle qu'elle justifie de qualifier la peine prononcée d'exagérément sévère. Les griefs invoqués sont donc vains.
3. Sur le vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable. Comme ses conclusions étaient vouées à l'échec, l'assistance judiciaire ne peut être accordée (cf. art. 64 al. 6 al. LTF) et le recourant doit supporter les frais, fixés en fonction de sa situation financière (art. 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, fixés à 800 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal valaisan, IIe Cour pénale.
Lausanne, le 13 janvier 2009
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Bendani