Verlängerung der Aufenthaltsbewilligung, hat sich ergeben:
A.- Der aus Mazedonien stammende S.D._, geboren am ......... 1953, arbeitete von 1989 an als Saisonnier in der Schweiz. Im November 1996 wurde seine Saisonbewilligung in eine Jahresaufenthaltsbewilligung zur Erwerbstätigkeit als Hilfsmaurer umgewandelt.
Seit dem 19. Juni 1997 war S.D._ infolge eines Arbeitsunfalles nicht mehr in der Lage, einer Erwerbstätigkeit nachzugehen. In der Folge wurde seine Aufenthaltsbewilligung zwecks Stellensuche letztmals bis zum 14. April 2000 verlängert. Mit Verfügung vom 12. Februar 1999 sprach die Schweizerische Unfallversicherungsanstalt (SUVA) S.D._ bei Anerkennung einer Erwerbsunfähigkeit von 40% eine monatliche Invalidenrente von Fr. 1'066.-- mit Wirkung ab dem 1. März 1999 zu und richtete ihm eine Integritätsentschädigung von Fr. 36'450.-- aus. Eine Beschwerde gegen diesen Entscheid ist beim Sozialversicherungsgericht des Kantons Zürich hängig. Die IV-Stelle der Sozialversicherungsanstalt des Kantons Zürich sprach S.D._ mit Verfügung vom 5. März 1999 in Anerkennung eines Invaliditätsgrades von 100% eine ganze Invalidenrente im Betrag von Fr. 489.-- pro Monat mit Wirkung ab dem 1. Juni 1998 und mit Verfügung vom 14. September 1999 eine Hilflosenentschädigung leichten Grades von Fr. 201.-- pro Monat mit Wirkung ab demselben Datum zu.
B.- Am 5. Februar 1999 reiste die Ehefrau M.D._ geboren am .......... 1958, - nachdem ihr zuvor die Einreise zwecks Familiennachzug verweigert worden war - mit einem Visum, welches sie zum Besuchsaufenthalt von längstens drei Monaten berechtigte, in die Schweiz ein.
Unter Hinweis auf die durch seine Invalidität verursachte Pflegebedürftigkeit stellte S.D._ am 7. April 1999 erneut ein Gesuch um Erteilung einer Aufenthaltsbewilligung für seine - auch nach Ablauf ihres Besuchsvisums weiterhin in der Schweiz weilende - Ehefrau. Mit Verfügung vom 25. Juni 1999 wies die Direktion für Soziales und Sicherheit des Kantons Zürich, Fremdenpolizei, das Gesuch ab mit der Begründung, die Voraussetzungen des Familiennachzugs seien aufgrund der fehlenden Erwerbstätigkeit von S.D._ (Art. 39 Abs. 1 lit. a der Verordnung vom 6. Oktober 1986 über die Begrenzung der Zahl der Ausländer, BVO; SR 823. 21) nicht gegeben und die geltend gemachten Gründe vermöchten keinen anderen Entscheid zu rechtfertigen. Dagegen erhob M.D._ Rekurs an den Regierungsrat des Kantons Zürich.
C.- Mit Verfügung vom 14. August 2000 wies die Direktion für Soziales und Sicherheit des Kantons Zürich, Fremdenpolizei, das Gesuch um Verlängerung der Aufenthaltsbewilligung für S.D._ ab und setzte ihm Frist zum Verlassen des Kantonsgebietes (Wegweisung). Zur Begründung führte die Fremdenpolizei an, die zuständige IV-Stelle habe den Invaliditätsgrad von S.D._ auf 100% festgelegt, weshalb mit einer Erwerbsaufnahme nicht mehr zu rechnen sei.
Da er zur Ausübung der Erwerbstätigkeit zugelassen worden sei und die Bewilligung eines erwerbslosen Aufenthalts nicht in Frage komme, müsse sein Aufenthaltszweck als "erfüllt" betrachtet werden. Im Übrigen sei seine persönliche Anwesenheit auch für das hängige Beschwerdeverfahren betreffend Unfallversicherung derzeit nicht erforderlich. Schliesslich habe S.D._ während längerer Zeit (durch die öffentliche Fürsorge) finanziell unterstützt werden müssen. Gegen diese Verfügung legte S.D._ Rekurs beim Regierungsrat des Kantons Zürich ein.
D.- Der Regierungsrat des Kantons Zürich vereinigte die gegen die Verfügungen vom 25. Juni 1999 bzw. vom 14. August 2000 gerichteten Rekurse von M. und S.D._ und wies sie mit Entscheid vom 21. März 2001 ab. Im Wesentlichen kam der Regierungsrat zum Schluss, auch bei einem weiteren Verbleib im Kanton Zürich sei mit einer Wiedereingliederung von S.D._ ins Erwerbsleben nicht zu rechnen, weshalb der Aufenthaltszweck des ursprünglich zur Ausübung einer Erwerbstätigkeit zugelassenen Ausländers hinfällig und die Verlängerung der Aufenthaltsbewilligung zu verweigern sei.
Da S.D._ nicht zwingend auf weitere medizinische Behandlung in der Schweiz angewiesen sei, sei ihm der Aufenthalt auch nicht unter diesem Titel (Art. 33 BVO) zu gestatten.
Schliesslich seien keine Umstände ersichtlich, welche die Anerkennung eines Härtefalles gemäss Art. 36 BVO rechtfertigen würden. Werde die Aufenthaltsbewilligung von S.D._ nicht verlängert, so komme eine Zulassung von M.D._ im Familiennachzug zum Vornherein nicht in Betracht.
E.- Mit Eingabe vom 2. Mai 2001 haben S. und M.D._ gemeinsam beim Bundesgericht staatsrechtliche Beschwerde eingereicht. Sie stellen den Antrag, der Beschluss des Regierungsrates des Kantons Zürich vom 21. März 2001 sei aufzuheben und das Verfahren an diesen zurückzuweisen; eventuell sei der Regierungsrat anzuweisen, die Aufenthaltsbewilligung der Beschwerdeführer zu verlängern.
Die Staatskanzlei des Kantons Zürich (im Auftrag des Regierungsrates) beantragt, auf die Beschwerde nicht einzutreten, eventualiter diese abzuweisen, soweit darauf einzutreten sei.
F.-Dem von den Beschwerdeführern gestellten Gesuch um aufschiebende Wirkung wurde mit Verfügung des Präsidenten der II. öffentlichrechtlichen Abteilung vom 23. Mai 2001 entsprochen.

Das Bundesgericht zieht in Erwägung:
1.-Die Beschwerdeführer haben staatsrechtliche Beschwerde erhoben. Dieses Rechtsmittel setzt - neben der Erschöpfung des kantonalen Instanzenzuges (Art. 86 OG) - voraus, dass die behauptete Rechtsverletzung nicht sonstwie durch Klage oder Rechtsmittel beim Bundesgericht oder einer anderen Bundesbehörde gerügt werden kann (Art. 84 Abs. 2 OG; Subsidiarität der staatsrechtlichen Beschwerde).
a) Mit der vorliegenden, gegen den Rekursentscheid des Regierungsrates gerichteten staatsrechtlichen Beschwerde wird - abgesehen von der behaupteten Verletzung des rechtlichen Gehörs (<ref-law>) - gerügt, dass die Verweigerung der streitigen Aufenthaltsbewilligungen gegen das Diskriminierungsverbot (<ref-law> bzw. Art. 14 in Verbindung mit Art. 3 EMRK), das Recht auf Achtung des Familienlebens (<ref-law> bzw. Art. 8 EMRK) sowie das Verbot unmenschlicher Behandlung (<ref-law> bzw.
Art. 3 EMRK) verstosse. Damit werden Einwendungen erhoben, die auf die Geltendmachung eines Rechtsanspruches auf die anbegehrten Aufenthaltsbewilligungen hinauslaufen. Solche Einwendungen sind nach einem kürzlich ergangenen Grundsatzentscheid des Bundesgerichts (<ref-ruling>) aufgrund der Subsidiaritätsregel von Art. 84 Abs. 2 OG im Verfahren der eidgenössischen Verwaltungsgerichtsbeschwerde zu erheben, unabhängig davon, ob der behauptete, nach Art. 100 Abs. 1 lit. b Ziff. 3 OG für die Zulässigkeit dieses Rechtsmittels massgebende Rechtsanspruch tatsächlich besteht. Der dargelegte Rechtsweg setzt sodann voraus, dass zuvor ein Entscheid der nach Art. 98a OG zuständigen kantonalen Gerichtsinstanz erwirkt wird, und zwar auch in Kantonen, in denen - wie im Kanton Zürich - dieses kantonale Rechtsmittel seinerseits nur bei Vorliegen eines Rechtsanspruches offen steht. Auf direkt gegen abschlägige Entscheide kantonaler Verwaltungsbehörden gerichtete staatsrechtliche Beschwerden, mit denen ein Rechtsanspruch auf die verweigerte ausländerrechtliche Bewilligung geltend gemacht wird, tritt das Bundesgericht - in Änderung der bisherigen Praxis - auch in Kantonen mit "anspruchsabhängigem" Rechtsmittel künftig nicht mehr ein (E. 1b sowie E. 2 S. 164 ff. des zitierten Entscheids).
b) Diese Rechtsprechung war den Beschwerdeführern bei Einreichung der staatsrechtlichen Beschwerde noch nicht bekannt. Ihre Eingabe ist daher nach der bisherigen Praxis zu behandeln. Danach ist zunächst zu prüfen, ob auf die anbegehrte Aufenthaltsbewilligung ein (grundsätzlicher) Rechtsanspruch besteht. Ist ein Anspruch gegeben, steht der Weg der eidgenössischen Verwaltungsgerichtsbeschwerde offen (Art. 100 Abs. 1 lit. b Ziff. 3 OG; <ref-ruling> E. 1a S. 62 f.; <ref-ruling> E. 2 S. 381, 425 E. 1 S. 427, mit Hinweisen), womit die Sache zur materiellen Beurteilung an das nach Art. 98a OG zuständige kantonale Gericht zu überweisen wäre (vgl. hiezu und zur bisherigen Praxis: <ref-ruling> E. 1c S. 147 f. sowie E. 3 S. 152; unveröffentlichte Urteile des Bundesgerichts vom 2. März 1999 i.S. Ferudun, E. 2c, vom 8. Juni 1998 i.S. Ringstad, E. 2, vom 28. Mai 1998 i.S. Puzo, E. 1, sowie vom 25. Mai 1998 i.S. Polak, E. 3). Besteht dagegen kein solcher Anspruch, fehlt es zur Anfechtung des abschlägigen Beschwerdeentscheids - von der Möglichkeit gewisser Verfahrensrügen abgesehen (<ref-ruling> E. 3b S. 86; <ref-ruling> E. 8e S. 398, je mit Hinweisen) - an der nach Art. 88 OG für die staatsrechtliche Beschwerde erforderlichen Legitimation (<ref-ruling> E. 1 S. 26; <ref-ruling> E. 1a S. 270; <ref-ruling> E. 2a S. 84 bzw. E. 7a S. 94; <ref-ruling> E. 8e S. 398).
2.- a) Gemäss Art. 4 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) entscheiden die zuständigen Behörden, im Rahmen der gesetzlichen Vorschriften und der Verträge mit dem Ausland, nach freiem Ermessen über die Bewilligung von Aufenthalt und Niederlassung. Es besteht damit grundsätzlich kein Anspruch auf Erteilung bzw. Verlängerung einer Aufenthaltsbewilligung, es sei denn, der Ausländer könne sich auf eine Sondernorm des Bundesrechts (einschliesslich Verfassungsrecht) oder eines Staatsvertrages berufen (<ref-ruling> E. 1a S. 62 f., 161 E. 1a S. 164; <ref-ruling> E. 2 S. 381, je mit Hinweisen).
b) Der Beschwerdeführer 1 verfügte bisher über eine Aufenthaltsbewilligung, die Beschwerdeführerin 2 lediglich über ein (abgelaufenes) Visum zum Besuchsaufenthalt. Dass die Beschwerdeführer aufgrund der Vorschriften des innerstaatlichen Gesetzesrechts oder eines bilateralen Staatsvertrages einen Anspruch auf Erteilung oder Verlängerung der Aufenthaltsbewilligung hätten, wird mit Grund nicht behauptet.
Ein allfälliger (indirekter) Anspruch könnte sich einzig aus den herangezogenen Garantien der Bundesverfassung bzw. der Europäischen Menschenrechtskonvention ergeben.
c) aa) Die Beschwerdeführer machen geltend, die Nichtverlängerung der Aufenthaltsbewilligung des Beschwerdeführers 1 verstosse gegen das Diskriminierungsverbot (<ref-law> sowie Art. 14 in Verbindung mit Art. 3 EMRK):
Durch die Praxis, die Aufenthaltsbewilligung von erwerbsunfähigen Ausländern, welche ursprünglich zur Ausübung einer Erwerbstätigkeit zugelassen wurden, nicht mehr zu verlängern, werde der Beschwerdeführer 1 in seiner Eigenschaft als Vollinvalider diskriminiert. Darüber hinaus liege auch eine indirekte Diskriminierung vor, da die Krankheitskosten, welche bei vollinvaliden Personen erwiesenermassen überdurchschnittlich hoch anfielen und vorliegend vorwiegend von der Krankenkasse nach Krankenversicherungsgesetz (KVG) übernommen werden müssten, nach einem Wegzug des Beschwerdeführers 1 ins Ausland - obwohl er über Jahre hinweg Prämien bezahlt und entsprechend Anspruch auf diese Leistungen habe - nicht mehr gedeckt würden. Auch kenne Mazedonien keine soziale Krankenversicherung und eine private Versicherung würde das Risiko einer bereits eingetretenen Invalidität nicht übernehmen. Insofern würde der Beschwerdeführer 1 durch die Nichtverlängerung seiner Aufenthaltsbewilligung faktisch von der für ihn notwendigen medizinischen Versorgung abgeschnitten, da er nicht in der Lage sei, aus seinen IV- und SUVA-Renten nebst seinem Lebensunterhalt auch die Krankheitskosten zu berappen. Schliesslich entfiele auch die ihm zugesprochene Hilflosenentschädigung der Invalidenversicherung, da diese nicht ins Ausland ausbezahlt würde.
bb) Das Bundesgericht hat sich in BGE <ref-ruling> E. 6 S. 392 ff. (bei vergleichbarer Konstellation) eingehend mit dem Diskriminierungsverbot befasst. Es besteht kein Anlass, von der dortigen Rechtsprechung abzuweichen. Ob jemand in der Schweiz eine Erwerbstätigkeit ausüben will, ist ein zulässiges und gebräuchliches Kriterium, von dem die Erteilung wie auch die Aufrechterhaltung einer Aufenthaltsbewilligung abhängig gemacht werden darf. Wer die Erwerbstätigkeit, derentwegen ihm die Aufenthaltsbewilligung in der Schweiz seinerzeit erteilt worden ist, nicht mehr ausübt oder ausüben kann, muss grundsätzlich in Kauf nehmen, dass ihm der weitere Aufenthalt in der Schweiz nicht mehr gestattet wird, es sei denn, abweichende spezielle Regelungen sähen ein entsprechendes Recht vor (vgl. etwa das Verbleiberecht gemäss Art. 4 des Anhangs I zum Abkommen zwischen der Europäischen Gemeinschaft und ihren Mitgliedstaaten einerseits und der Schweizerischen Eidgenossenschaft andererseits über die Freizügigkeit [BBl 1999 S. 7027 ff.] und dazu die bundesrätliche Botschaft in BBl 1999 S. 6311 sowie Minh Son Nguyen, L'accord bilatéral sur la libre circulation des personnes et le droit de la police des étrangers, in: RDAF 2001 1 S. 168). Dass diese Konsequenz auch invalid gewordene Ausländer treffen kann, wenn sie noch kein festes Anwesenheitsrecht erworben haben, liegt in der Natur der Sache und stellt keine verbotene (direkte oder indirekte) Diskriminierung dieser Bevölkerungsgruppe dar. Der Hinweis auf die mutmasslich grösseren Krankheitskosten einer vollinvaliden Person und auf das Risiko, dass die diesbezüglichen Sozialversicherungsleistungen im Heimatland Mazedonien allenfalls ungenügend sein könnten, vermag den Vorwurf der Diskriminierung ebenfalls nicht zu begründen. Nachteile dieser Art drohen dem Beschwerdeführer 1 nicht wegen der auf ihn angewandten ausländerrechtlichen Regelung, sondern wegen der speziellen Verhältnisse in seinem Heimatland. Soweit der Beschwerdeführer 1 Anspruch auf Leistungen der schweizerischen Invalidenversicherung hat, können diese nach Mazedonien ausbezahlt werden (vgl. Art. 8 lit. f des Abkommens vom 8. Juni 1962 zwischen der Schweizerischen Eidgenossenschaft und der Föderativen Volksrepublik Jugoslawien über Sozialversicherung [SR 0.831. 109.818. 1; Fassung gemäss Zusatzabkommen vom 9. Juli 1982], welches bis zum Inkrafttreten des am 9. Dezember 1999 abgeschlossenen Abkommens zwischen der Schweizerischen Eidgenossenschaft und der Republik Mazedonien über Soziale Sicherheit weiterhin Anwendung findet [siehe dazu die Botschaft in BBl 2001 S. 2135]; vgl. auch <ref-ruling> E. 7c S. 118 ff.). Nach dem Gesagten können die Beschwerdeführer aus dem in <ref-law> bzw.
Art. 14 EMRK verankerten Diskriminierungsverbot keinen Anspruch auf Erteilung bzw. Verlängerung der Aufenthaltsbewilligung ableiten.
d) aa) Die Beschwerdeführer rügen einen Verstoss gegen das in <ref-law> bzw. Art. 3 EMRK verankerte Verbot unmenschlicher Behandlung. Einerseits sei der Beschwerdeführer 1 aufgrund seines medizinischen Beschwerdebildes, welches als äusserst komplex bezeichnet werden müsse, auf umfangreiche medizinische Behandlungen angewiesen; insbesondere werde er wegen seiner diagnostizierten Diabetes sein Leben lang von Medikamenten abhängig sein, wofür jedoch in Mazedonien keine Krankenkasse aufkomme. Auf der anderen Seite sei es bereits bei Ausfällung des angefochtenen Entscheids notorisch gewesen, dass in Mazedonien bürgerkriegsähnliche Auseinandersetzungen herrschten, deren Folgen der Beschwerdeführer 1 unmittelbar ausgeliefert wäre, da er in seinem Zustand nur schwerlich die Flucht ergreifen könne; sodann sei in Zeiten des Konflikts die Auszahlung von Renten aus der Schweiz nicht gewährleistet. Mit Blick auf die fehlende soziale Absicherung und die damit verbundene Unerreichbarkeit der medizinischen Versorgung stelle die Wegweisung des Beschwerdeführers 1 in sein Heimatland eine unmenschliche Behandlung dar.
bb) Aus Art. 3 EMRK bzw. <ref-law> (spezifischer:
<ref-law>) lässt sich kein Anspruch auf Erteilung einer Aufenthaltsbewilligung ableiten; diese Garantie steht unter gewissen Voraussetzungen allenfalls der Ausschaffung in ein bestimmtes Land entgegen, vermittelt aber kein Recht auf Aufenthalt (nicht veröffentlichte Urteile des Bundesgerichts vom 15. Dezember 1994 i.S. Jovanovic, E. 1a, vom 7. November 1994 i.S. Miletic, E. 1a, vom 16. Februar 1993 i.S. Yildiz, E. 2b, sowie vom 25. November 1989 i.S. Ikizer, E. 2d; vgl. Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in RDAF 1997 1 S. 306; Mark E. Villiger, Handbuch der Europäischen Menschenrechtskonvention [EMRK],
2. Aufl. , Zürich 1999, S. 192 N. 297). Hinsichtlich der von den kantonalen Behörden verfügten Wegweisung ist die Verwaltungsgerichtsbeschwerde - unabhängig vom Vorliegen allfälliger grundrechtlicher Rechtsansprüche - aufgrund von Art. 100 Abs. 1 lit. b Ziff. 4 OG (absolut) ausgeschlossen, weshalb diese Rüge im Verfahren der staatsrechtlichen Beschwerde (Art. 84 Abs. 2 OG) zu prüfen ist (unten E. 4).
e) Schliesslich liegt auch kein Verstoss gegen das in <ref-law> sowie Art. 8 EMRK verankerte Recht auf Achtung des Familienlebens vor, da dem Beschwerdeführer 1 - nach dem Gesagten - kein Rechtsanspruch auf die Aufenthaltsbewilligung zusteht und damit keiner der beiden Beschwerdeführer über das nach ständiger Rechtsprechung für die Berufung auf diese Garantie erforderliche gefestigte Anwesenheitsrecht verfügt (BGE <ref-ruling> E. 2b S. 382 ff. mit Hinweisen). Der angefochtene Entscheid, der die Aufenthaltsbewilligung gegenüber beiden Beschwerdeführern verweigert, verunmöglicht oder erschwert ihnen das weitere familiäre Zusammenleben nicht. Dass die Ehefrau bei einem Aufenthalt in der Schweiz allenfalls in den Genuss rentenrechtlicher Vorteile käme, ändert nichts.
3.- a) Haben die Beschwerdeführer nach dem Gesagten keinen Rechtsanspruch auf Erteilung einer Aufenthaltsbewilligung, so bleibt die Verwaltungsgerichtsbeschwerde ausgeschlossen. Auf die staatsrechtliche Beschwerde gegen den regierungsrätlichen Beschluss ist, soweit die Nichtverlängerung der Aufenthaltsbewilligung an den Beschwerdeführer 1 bzw. deren Verweigerung an die Beschwerdeführerin 2 in der Sache angefochten wird, mangels Legitimation nicht einzutreten (E. 1b).
b) Trotz fehlender Legitimation in der Sache sind die Beschwerdeführer befugt, eine Verletzung jener Verfahrensgarantien geltend zu machen, deren Missachtung eine formelle Rechtsverweigerung darstellt (sog. "Star-Praxis", grundlegend: <ref-ruling> E. 3c S. 312 f.; <ref-ruling> E. 3b S. 86 sowie E. 7b S. 94; <ref-ruling> E. 1 S. 26 f.). Dabei sind aber Rügen nicht zu hören, die im Ergebnis auf eine materielle Überprüfung des Bewilligungsentscheids abzielen, so etwa die Behauptung, Beweisanträge seien wegen Unerheblichkeit oder willkürlicher antizipierter Beweiswürdigung abgelehnt worden und die Begründung des angefochtenen Entscheids sei unvollständig oder zu wenig differenziert ausgefallen und setze sich nicht mit sämtlichen von den Parteien erhobenen Argumenten auseinander (vgl. <ref-ruling> E. 1c S. 236; <ref-ruling> E. 4a S. 95; <ref-ruling> E. 3c S. 313).
c) aa) Die Beschwerdeführer machen eine Verletzung ihres Anspruches auf rechtliches Gehör (<ref-law>) geltend, welche sie darin erblicken, dass es die Direktion für Soziales und Sicherheit unterlassen habe, den Beschwerdeführer 1 vor Erlass ihrer Verfügung vom 14. August 2000 über die beabsichtigte Nichtverlängerung seiner Aufenthaltsbewilligung zu orientieren, und ihm damit die Möglichkeit genommen habe, sich vorgängig dazu zu äussern. Im angefochtenen Entscheid nimmt der Regierungsrat den Standpunkt ein, eine allfällige Gehörsverletzung durch die Direktion sei im Rekursverfahren geheilt worden, was die Beschwerdeführer als unzutreffend erachten. Diese Rüge erweist sich als im Rahmen der "Star-Praxis" zulässig. Nicht zu hören ist dagegen der Einwand der Beschwerdeführer, es liege eine Verletzung der Begründungspflicht vor, da die Direktion in der Verfügung vom 14. August 2000 nicht auf vorgängig bei ihr eingereichte Unterlagen des Beschwerdeführers 1 eingegangen sei, steht diese Rüge doch mit der materiellen Würdigung des Falles im Zusammenhang.
bb) Aus den Vorakten ergibt sich, dass der Beschwerdeführer 1 am 24. März 2000 (auf dem entsprechenden Formular) ein Gesuch um Verlängerung seiner Aufenthaltsbewilligung stellte. Auf Aufforderung der Direktion für Soziales und Sicherheit reichte er am 2. Mai 2000 verschiedene seine gesundheitliche Verfassung sowie die sozialversicherungsrechtlichen Gegebenheiten dokumentierende Unterlagen zu den Akten. Die Direktion für Soziales und Sicherheit unterliess es in der Folge, dem Beschwerdeführer 1 ein (sich in den Akten befindendes) Schreiben vom 14. Juli 2000 zuzustellen, in welchem sie ihn über den beabsichtigten Entscheid orientiert und ihm "im Sinne des rechtlichen Gehörs" Gelegenheit gegeben hätte, sich dazu schriftlich zu äussern, was er infolgedessen nicht getan hat (vgl. den entsprechenden Vermerk in der Verfügung vom 14. August 2000). Im Rahmen des Rekursverfahrens stellte die Staatskanzlei des Kantons Zürich dem Beschwerdeführer das erwähnte Schreiben der Direktion für Soziales und Sicherheit zu und bot ihm Gelegenheit zur Stellungnahme, wovon er mit Eingabe vom 7. Dezember 2000 Gebrauch gemacht hat.
cc) Indem es die Direktion für Soziales und Sicherheit unterlassen hat, den Beschwerdeführer 1 über die beabsichtigte Verfügung ins Bild zu setzen und ihm Gelegenheit zur Stellungnahme zu geben, ist ihr zwar ein gravierendes Versehen unterlaufen. Die Beschwerdeführer hatten jedoch Gelegenheit, sämtliche Einwendungen im Verfahren vor dem Regierungsrat vorzubringen, dem in der streitigen Angelegenheit eine umfassende Kognition zustand (vgl. § 20 des Zürcher Verwaltungsrechtspflegegesetzes vom 24. Mai 1959) und der den Fall auch tatsächlich selber einlässlich prüfte.
Damit waren die Voraussetzungen für eine Heilung der Gehörsverletzung gegeben (vgl. Alfred Kölz/Jürg Bosshart/Martin Röhl, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Aufl. , Zürich 1999, § 20 N. 16). Zu berücksichtigen ist auch, dass es sich bei der unterbliebenen Einladung zur Stellungnahme um ein klares Versehen der Direktion handelte; es liegt somit kein Fall einer erstinstanzlichen Behörde vor, welche darauf vertraut, dass von ihr missachtete Verfahrensrechte systematisch nachträglich geheilt würden (vgl. <ref-ruling> E. 6b/aa S. 123 f.), was eine Aufhebung der Verfügung aus grundsätzlichen Überlegungen nahe gelegt hätte. Dass eine Rekursinstanz in einem Fall der vorliegenden Art sich auch zu einer Rückweisung (statt Heilung) veranlasst sehen könnte, lässt das Vorgehen des Regierungsrates nicht als verfassungswidrig erscheinen.
4.- a) Soweit sich die Beschwerdeführer gegen die Wegweisung wenden, indem sie geltend machen, diese verstosse gegen Art. 3 EMRK bzw. <ref-law> (oben E. 2d/aa), sind sie grundsätzlich zur staatsrechtlichen Beschwerde legitimiert (Art. 88 OG).
b) Nach Art. 3 EMRK (bzw. <ref-law>) darf niemand der Folter oder unmenschlicher oder erniedrigender Strafe oder Behandlung unterworfen werden. Die erwähnte Garantie kann bereits verletzt sein, wenn eine Person in ein Land abgeschoben wird, in welchem ihr mit erheblicher Wahrscheinlichkeit eine Art. 3 EMRK verletzende Behandlung droht; dieser in der Rechtsprechung der Strassburger Organe entwickelte (indirekte) Teilgehalt von Art. 3 EMRK fand Eingang in die bundesgerichtliche Rechtsprechung (vgl. <ref-ruling> E. 2a S. 71; <ref-ruling> E. 4b S. 112; <ref-ruling> E. 2d S. 283 f., 511 E. 6a S. 521) und mit <ref-law> seinen Niederschlag im positiven schweizerischen Verfassungsrecht (Villiger, a.a.O., S. 194 N. 299; Ulrich Häfelin/ Walter Haller, Schweizerisches Bundesstaatsrecht, 5. Aufl. , Zürich 2001, S. 171 N. 592 f.; Jörg Paul Müller, Grundrechte in der Schweiz, 3. Aufl. , Bern 1999, S. 24; BBl 1997 I 171).
Nach der Rechtsprechung kann eine Verletzung von Art. 3 EMRK auch dann in Frage stehen, wenn ein Ausländer in ein Land ausgeschafft wird, in dem eine für ihn (lebens-)notwendige medizinische Behandlung nicht gewährleistet ist (Urteil des Europäischen Gerichtshofs für Menschenrechte i.S. D. c.
Vereinigtes Königreich vom 2. Mai 1997, Rec. 1997-III S. 777 ff. Ziff. 46-54 S. 791 ff.; Nichtzulassungsentscheid der Europäischen Kommission für Menschenrechte i.S.
Y.E. c. Schweiz vom 13. März 1998; nicht veröffentlichtes Urteil des Bundesgerichts vom 7. November 1994 i.S. Miletic, E. 2b).
c) Streitgegenstand des vorliegenden Verfahrens bildet die Verweigerung der Aufenthaltsbewilligung sowie die Wegweisung aus dem Kanton. Mit Erlass dieser Anordnungen steht indessen noch nicht automatisch fest, wohin sich der Betroffene zu begeben hat. Die Frage einer Verletzung von Art. 3 EMRK (bzw. <ref-law>) kann sich erst dann stellen, falls eine zwangsweise Ausschaffung durchgeführt werden soll, welche aufgrund der dannzumaligen konkreten Umstände mit einer Gefahr für Leib und Leben des Betroffenen verbunden ist (vgl. Villiger, a.a.O., S. 195 N. 301, mit Hinweisen in Fn. 87). Im Übrigen durfte der Regierungsrat zulässigerweise davon ausgehen, dass die minimal erforderliche ärztliche Versorgung des Beschwerdeführers 1 auch in Mazedonien bzw. von den dort angrenzenden Ländern aus möglich sein wird. Entgegen der von den Beschwerdeführern vertretenen Auffassung besteht in Mazedonien eine Krankenpflegeversicherung, welche in der Praxis im Rahmen der obligatorischen (unter staatlicher Aufsicht geführten) Grundversicherung Versicherungsdeckung für die ganze Wohnbevölkerung bietet; die Krankenpflege ist damit, von gewissen Selbstbehalten abgesehen, unentgeltlich (vgl. zum Ganzen die Botschaft betreffend das Abkommen zwischen der Schweiz und Mazedonien über Soziale Sicherheit, in: BBl 2001 S. 2137 sowie 2144). Von einer für den Beschwerdeführer 1 unerreichbaren medizinischen Versorgung kann daher nicht gesprochen werden.
5.- Damit ist die staatsrechtliche Beschwerde, soweit darauf einzutreten ist, abzuweisen.
Den Beschwerdeführern sind, entsprechend dem Verfahrensausgang, die Kosten des bundesgerichtlichen Verfahrens aufzuerlegen, unter solidarischer Haftung (Art. 156 Abs. 1 und 7 in Verbindung mit Art. 153 und 153a OG). Auf die Zusprechung einer Parteientschädigung besteht kein Anspruch (vgl. Art. 159 Abs. 2 OG analog).

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Die Gerichtsgebühr von Fr. 2'000.-- wird den Beschwerdeführern auferlegt, unter solidarischer Haftung.
3.- Dieses Urteil wird den Beschwerdeführern und dem Regierungsrat (Staatskanzlei) des Kantons Zürich schriftlich mitgeteilt.
_
Lausanne, 29. August 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: