Faits: A.a. X._, ressortissant serbe (Kosovo), né en 1978, a obtenu le 3 septembre 1993 une autorisation de séjour pour regroupement familial. En 2001 et 2002, l'intéressé a été condamné à des peines d'emprisonnement de 33 mois, respectivement de 15 jours, pour vols, tentatives de vol, violations de domicile, dommages à la propriété, entrave à l'action pénale, vol d'usage, viol et actes d'ordre sexuel avec une mineure. Par arrêt du 27 octobre 2003, le Tribunal administratif du canton de Fribourg a confirmé la décision du 17 juin 2003 du Service de la population et des migrants du canton de Fribourg refusant le renouvellement de l'autorisation de séjour et prononçant l'expulsion de X._. La décision d'expulsion du canton de Fribourg prononcée pour une durée indéterminée a été étendue à tout le territoire de la Confédération par l'office fédéral compétent en date du 31 mars 2004. X._ a quitté la Suisse cette année-là. A.b. Le 3 février 1998, X._ a eu un fils, Z._, né d'une union avec une compatriote qui s'est soldée par un divorce en 2004. L'enfant a été confié à la garde de la mère. D'une relation avec Y._, une compatriote titulaire d'une autorisation d'établissement, X._ a eu deux autres enfants: A._, née en 1999, et B._, né en 2001. Le 10 février 2006, X._ a épousé Y._. Le couple a eu un troisième enfant, C._, née en 2006. Par arrêt du 14 mai 2007, le Tribunal administratif du canton de Vaud (ci-après: le Tribunal cantonal) a confirmé la décision du Service de la population du canton de Vaud (ci-après: le Service cantonal) du 31 août 2006 refusant de délivrer une autorisation d'entrée respectivement de séjour pour regroupement familial en faveur de l'intéressé, notamment compte tenu de l'intérêt public à maintenir éloigné un délinquant ayant gravement enfreint l'ordre public. Le Tribunal cantonal, par arrêt du 17 décembre 2007, a rejeté le recours de X._ dirigé contre la décision du Service cantonal du 2 août 2007 refusant d'entrer en matière sur une demande de réexamen. A.c. Après avoir été refoulé dans son pays d'origine en 2007, X._ est revenu illégalement en Suisse, le 15 avril 2008, et a déposé une nouvelle demande de regroupement familial, considérée comme seconde demande de réexamen par le Service cantonal et jugée irrecevable le 29 juillet 2008. Par arrêt du 14 octobre 2008, le Tribunal cantonal a confirmé la décision précitée du 29 juillet 2008. Le Tribunal fédéral a, le 4 mars 2009 (cause 2C_838/2008), déclaré le recours de X._ irrecevable. A.d. Le 28 janvier 2010, X._ a sollicité une nouvelle demande d'autorisation de séjour. Traitant à nouveau cette requête comme une demande de réexamen, le Service cantonal a considéré qu'elle était irrecevable par décision du 21 avril 2010. Il a en outre décidé que X._ devait sans délai quitter la Suisse. Le Tribunal cantonal a rejeté le recours formé à l'encontre de cette décision par arrêt du 4 août 2011. Le 2 mai 2012, le Tribunal fédéral a rejeté le recours contre cet arrêt (cause 2C_715/2011). A.e. X._ a quitté le territoire suisse le 5 juin 2012. B. Le 20 juillet 2012, X._ a déposé auprès de l'Ambassade de Suisse au Kosovo une demande d'entrée et de séjour en Suisse. A l'appui de sa demande, il a fait état de l'obtention par sa fille A._ de la nationalité suisse le 3 juillet 2012. Traitant cette nouvelle requête comme une demande de réexamen, le Service cantonal l'a rejetée par décision du 22 novembre 2012, tout en acceptant d'entrer en matière. Par arrêt du 18 mars 2013, le Tribunal cantonal a rejeté le recours de l'intéressé, de Y._ et de leurs enfants. Il a considéré que compte tenu de la gravité des infractions retenues contre l'intéressé et du fait que ce dernier contestait de manière systématique les décisions rendues à son endroit, l'obtention par sa fille de la nationalité suisse ne remettait pas en cause la pesée des intérêts opérée par les différentes autorités. C. X._et Y._, ainsi que leurs trois enfants, forment un recours en matière de droit public et un recours constitutionnel subsidiaire contre l'arrêt du Tribunal cantonal du 18 mars 2013. Ils demandent, sous suite de frais et dépens, l'annulation de l'arrêt entrepris et l'admission de la demande de reconsidération, subsidiairement, le renvoi de la cause au Tribunal cantonal pour que celui-ci admette la demande de reconsidération. Le Service cantonal a renoncé à déposer des observations. Le Tribunal cantonal se réfère à son arrêt du 18 mars 2013. L'Office fédéral des migrations conclut au rejet du recours. Les recourants se sont encore prononcés par écriture du 12 juillet 2013. 