Faits :
A.
Ressortissant bulgare né en 1963, A.X._ a séjourné et travaillé illégalement en Suisse d'avril 1998 à novembre 2003, alors qu'il était titulaire d'un passeport de Macédoine. Le 11 décembre 2003, le Service de la population et des migrants de l'Etat de Fribourg (ci-après: le Service cantonal) a prononcé son refoulement et l'intéressé a quitté la Suisse au début du mois de janvier 2004. Le 2 mars 2004, l'Office fédéral des migrations a rendu à son encontre une décision d'interdiction d'entrée en Suisse valable jusqu'au 1er mars 2007; le 21 mars 2004, A.X._ a été condamné pour infraction à la législation fédérale sur le séjour et l'établissement des étrangers (aLSEE) à 30 jours d'emprisonnement avec sursis pendant deux ans et à une amende de 1'000 fr.
Au mois de janvier 2007, A.X._ est revenu en Suisse et y a travaillé sans autorisation. Son épouse, B.X._, ressortissante bulgare, l'a rejoint le 15 août 2007, elle aussi sans disposer de titre de séjour. Le couple n'a plus quitté la Suisse depuis lors. A la suite d'une dénonciation, les deux conjoints ont été condamnés pénalement pour ces faits.
Le 18 janvier 2011, la Section main-d'oeuvre étrangère du Service cantonal a rejeté la demande de prise d'emploi de la société C._ SA en faveur de A.X._, en raison du non-respect de la priorité de la main-d'oeuvre indigène; la société a en outre été avisée que A.X._ devait être licencié. Non contestée, cette décision est entrée en force. Une deuxième demande de prise d'emploi, déposée par la même société, a été rejetée le 20 juillet 2011, l'employeur ayant confirmé par écrit qu'il renonçait à engager l'intéressé. Cette décision n'a pas non plus été contestée.
Le Service de l'emploi du canton de Vaud a rejeté deux demandes d'engagement de A.X._, l'une le 13 décembre 2011, formée par D._ SA, l'autre, le 18 avril 2012, déposée par C._ SA, pour non-respect du principe de la priorité de la main-d'oeuvre indigène.
Le 26 juin 2012, A.X._ a déposé auprès des autorités fribourgeoises une nouvelle demande d'autorisation de séjour; il a signé un nouveau contrat de travail avec C._ SA le 12 juillet 2012 et cette société a de nouveau demandé une prise d'emploi, qui a été rejetée pour le même motif que précédemment, par décision du 4 septembre 2012 qui n'a pas été contestée. La société a confirmé qu'elle avait renoncé à engager l'intéressé.
B.
Parallèlement, A.X._ et B.X._ ont déposé, le 9 décembre 2010, une requête d'autorisation de séjour avec activité lucrative en faveur du mari et au titre de regroupement familial pour l'épouse, en faisant valoir leurs droits issus de leur appartenance à l'Union européenne liée à leur nationalité bulgare. A.X._ a réitéré sa demande le 26 juin 2012, en faisant valoir qu'il était resté en Suisse depuis le 1er janvier 2007.
Cette requête a été rejetée le 11 novembre 2013 par le Service cantonal, qui a prononcé le renvoi du couple et leur a imparti un délai de 30 jours pour quitter la Suisse. Statuant sur recours des époux X._, le Tribunal cantonal de l'Etat de Fribourg (ci-après: le Tribunal cantonal) a confirmé cette décision par arrêt du 19 mars 2014.
C.
A l'encontre de cet arrêt, A.X._ (le recourant 1) et B.X._ (la recourante 2) forment un recours en matière de droit public au Tribunal fédéral. Ils concluent, sous suite de frais et dépens, à l'admission du recours, à l'annulation de l'arrêt entrepris et, principalement, à ce que le recourant 1 soit mis au bénéfice d'une autorisation de séjour avec activité lucrative et à ce que la recourante 2 soit mise au bénéfice d'une autorisation de séjour au titre de regroupement familial. Subsidiairement, ils proposent le renvoi de la cause au Service cantonal ou à l'autorité intimée pour nouvelle décision dans le sens des considérants. Ils requièrent par ailleurs l'effet suspensif.
Il n'a pas été ordonné d'échange d'écritures.

Considérant en droit :
1.
1.1. Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral, ni le droit international ne donnent droit. Selon la jurisprudence, si l'intéressé a potentiellement droit à une autorisation de séjour sur la base de l'Accord sur la libre circulation des personnes (ALCP; RS 0.142.112.681), le Tribunal fédéral entre en matière du seul fait que celui-ci est un ressortissant de l'Union européenne, examinant ensuite avec le fond si la convention confère effectivement un tel droit (<ref-ruling> consid. 1.1 p. 179; <ref-ruling> consid. 1.2 p. 343). Cette pratique s'applique également aux ressortissants de l'Union européenne soumis au régime transitoire prévu par l'art. 10 ALCP (arrêts 2D_50/2012 du 1er avril 2013 consid. 1.3 et 1.4; 2C_268/2012 du 23 mars 2012 consid. 2.3.1; 2C_217/2009 du 11 septembre 2009 consid. 1.2 et 1.3).
Les recourants sont de nationalité bulgare et tombent donc sous le coup du régime transitoire prévu par l'art. 10 al. 2b ALCP. Ce régime, qui lie la Suisse et, entre autres parties contractantes, la République de Bulgarie (cf. Protocole II à l'ALCP du 27 mai 2008; RS 0.142.112.681.1), permet de maintenir à l'égard des travailleurs de l'autre partie contractante employés sur leur territoire, les contrôles de la priorité du travailleur intégré dans le marché régulier du travail et des conditions de salaire et de travail. Prolongée une première fois jusqu'au 31 mai 2014, la période transitoire s'étend désormais, comme l'a retenu pertinemment l'autorité cantonale contrairement à ce qu'affirment les recourants, jusqu'au 31 mai 2016 (RO 2014 1893). Partant, la voie du recours en matière de droit public est en principe ouverte.
1.2. Déposé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites par la loi (art. 42 LTF), par les destinataires de l'arrêt attaqué qui ont qualité pour recourir (art. 89 al. 1 LTF), le présent recours, dirigé contre une décision finale (art. 90 LTF) rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF), est recevable.
2.
La motivation présentée pour contester le refus d'octroyer une autorisation de séjour par les recourants est toutefois manifestement infondée, de sorte qu'il convient de la rejeter sur la base d'une motivation sommaire (cf. art. 109 al. 2 let. a et al. 3 LTF).
2.1. Dans un premier grief, les recourants invoquent une violation de l'art. 8 CEDH sous l'angle de leur vie privée et familiale. Ils font uniquement valoir leur long séjour en Suisse, leur difficulté de réintégration en cas de retour en Bulgarie ou en Macédoine et leur bonne intégration.
Comme ils ne se prévalent d'aucun lien étroit et effectif avec une personne de leur famille ayant un droit de résider durablement en Suisse, on ne voit pas que l'art. 8 par. 1 CEDH puisse leur donner un droit sous cet angle (cf. <ref-ruling> consid. 1.3 p. 145 s.). Quant à leur vie privée, son ingérence au sens de l'art. 8 par. 1 CEDH suppose la réalisation de circonstances exceptionnelles (cf. <ref-ruling> consid. 3.2 p. 250 ss) que les recourants ne font nullement valoir. Le fait qu'ils aient vécu en Suisse pendant plusieurs années, mais toujours dans l'illégalité (cf., au sujet de la prise en compte limitée d'un séjour passé dans l'illégalité, <ref-ruling> consid. 4.2 p. 8; arrêt 2C_977/2012 du 15 mars 2013 consid. 3.6), au mépris des décisions de renvoi, d'interdiction d'entrée et de travailler, ainsi que des condamnations pénales dont ils ont fait l'objet, ne saurait constituer de telles circonstances.
2.2. Dans une seconde critique, les recourants reprochent aux autorités cantonales d'avoir violé les art. 1 et 10 ALCP. Ils soutiennent que l'entreprise C._ SA ne trouve pas de main-d'oeuvre locale, raison pour laquelle elle a formulé plusieurs demandes de prise d'emploi en faveur du recourant 1 et qu'elle continue du reste d'employer celui-ci. D'après les recourants, l'absence de recours de ladite entreprise contre les décisions administratives refusant ses requêtes ne peut être retenue à leur encontre.
La mise en oeuvre de l'Accord sur la libre circulation des personnes est réglée par l'ordonnance sur l'introduction de la libre circulation des personnes du 22 mai 2002 (ci-après: OLCP; RS 142.203; arrêt 2C_217/2009 du 11 septembre 2009 consid. 2.1). Conformément à l'art. 27 OLCP, intitulé " Décision préalable à l'octroi de l'autorisation ",
" avant que les autorités cantonales compétentes n'accordent à un ressortissant de Bulgarie ou de Roumanie une autorisation en vue de l'exercice d'une activité lucrative salariée, l'autorité cantonale du marché du travail rend une décision précisant que les conditions relatives au marché du travail sont remplies...".
Il découle du titre et du texte de cette disposition que l'existence d'une décision émanant des autorités compétentes en matière de marché du travail est une condition préalable à l'octroi de l'autorisation de séjour. L'art. 21 al. 1 LEtr, applicable, au moins par analogie, à l'admission en vue de l'exercice d'une activité lucrative en Suisse des ressortissants des nouveaux Etats membres de l'Union européenne (arrêt 2C_217/2009 du 11 septembre 2009 consid. 2.2), prévoit aussi qu'un étranger ne peut être admis en vue de l'exercice d'une activité lucrative que s'il est démontré qu'aucun travailleur en Suisse ni aucun ressortissant d'un Etat avec lequel a été conclu un accord sur la libre circulation des personnes correspondant au profil requis n'a pu être trouvé. L'existence d'une décision précisant que les conditions relatives au marché du travail sont remplies au sens de l'art. 27 OLCP apporte cette preuve.
En l'espèce, il ressort des constatations cantonales, qui lient le Tribunal fédéral (art. 105 al. 1 LTF), que la société auprès de laquelle, comme le concède le recourant 1 lui-même, il serait encore employé sans aucune autorisation, a formé quatre requêtes préalables de prises d'emploi en sa faveur. Les autorités tant fribourgeoises que vaudoises en matière de marché du travail ont rejeté ces requêtes par des décisions entrées en force sans avoir été contestées, en raison du non-respect du principe de priorité de la main-d'oeuvre indigène. Une autre société a également formé une demande au Service de l'emploi du canton de Vaud, qui a subi un sort identique pour le même motif. Partant, le recourant 1 ne peut se prévaloir d'aucune décision émanant d'une autorité cantonale du marché du travail considérant que les conditions relatives au marché du travail sont remplies. La condition préalable au sens de l'art. 27 OLCP permettant au recourant 1 d'obtenir un titre de séjour fait ainsi défaut. Contrairement à ce que souhaiteraient les recourants, il n'est pas possible, dans le cadre de la procédure concernant l'octroi d'un titre de séjour devant les autorités en matière de droit des étrangers, de revenir sur des décisions entrées en force émanant des autorités cantonales compétentes dans le domaine du marché du travail. Partant, l'appréciation par ces dernières du principe de priorité de la main-d'oeuvre indigène ne peut être remise en cause dans la présente procédure.
2.3. C'est ainsi sans violer l'art. 8 CEDH et en conformité avec l'ALCP ainsi que les dispositions régissant sa mise en oeuvre que le Tribunal cantonal a confirmé le refus d'octroyer au recourant 1 une autorisation de séjour. Son épouse ne pouvant se prévaloir que d'un droit dérivé, on ne peut davantage reprocher à l'arrêt attaqué de lui avoir également refusé l'octroi d'un titre de séjour.
Le recours ne peut donc qu'être rejeté. Cette conclusion rend sans objet la demande d'effet suspensif.
3.
Compte tenu de l'issue du litige, les frais seront mis à la charge des recourants, solidairement entre eux (art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (art. 68 al. 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3.
Le présent arrêt est communiqué au mandataire des recourants, au Service de la population et des migrants, au Tribunal cantonal de l'Etat de Fribourg, Ie Cour administrative, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 7 août 2014
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Le Greffier :
Zünd Chatton