Sachverhalt:
A.
C._ und D._ sind die Eltern der 2010 geborenen A._ und der 2015 geborenen B._. Die Familie lebte in U._ (Österreich).
Im Jahr 2017 begannen eheliche Probleme. Zufolge Arbeitslosigkeit und zur Behebung des finanziellen Engpasses nahm der Vater im Dezember 2017 eine Anstellung bei einer Firma in Bern an und zog im Frühling 2018 in die Schweiz. Da sich die Familie nicht zwei Wohnungen leisten konnte, musste die Familienwohnung in U._ aufgegeben werden und die Mutter mit den beiden Kindern zu den Eltern väterlicherseits ziehen.
Die mit der Situation überforderte Mutter (polizeiliche Androhung der Ausweisung zufolge fehlender Meldung; prekäre finanzielle Verhältnisse; gespanntes Verhältnis zwischen ihr und den Eltern väterlicherseits) begab sich am 21. Juli 2018 nach Florenz, um die Hilfe ihrer dort lebenden Brüder in Anspruch zu nehmen. Dabei liess sie die beiden Kinder in der Obhut der Grosseltern. Weil sie in der Folge mehrere Tage wegblieb, fuhr der nach Österreich zurückgereiste Vater mit den beiden Kindern am 28. Juli 2018 ebenfalls nach Florenz, wo er aber die Mutter nicht auffinden konnte, und anschliessend mit den Kindern direkt in die Schweiz. Am 29. Juli 2018 kehrte die Mutter zurück und stellte fest, dass die Kinder nicht mehr vor Ort anzutreffen waren.
Eine Woche darauf konnte sie durch Vermittlung von Kollegen eine eigene Wohnung beziehen. Gleichzeitig wandte sie sich an die Polizei und wenige Tage später an das Bezirksgericht U._.
B.
Am 5. September 2018 stellte die Mutter schliesslich einen Rückführungsantrag, welcher über die österreichische Zentralbehörde an die schweizerische Zentralbehörde gelangte, wo er am 11. September 2018 eintraf. Trotz der anschliessend intensiven Suchbemühungen der Polizei (verdeckte Ermittlung während des Tages wie auch während der Nacht) konnten die Kinder am Wohnort des Beschwerdeführers in der Schweiz bis zum Frühling 2019 nicht aufgefunden werden; sie waren bis dahin auch nicht gemeldet und die ältere Tochter auch nicht eingeschult.
Am 26. März 2019 stellte die Mutter schliesslich beim Obergericht des Kantons Solothurn das Rückführungsgesuch. Mit Urteil vom 14. Mai 2019 ordnete das Obergericht die Rückführung der beiden Kinder nach Österreich an, wobei es dem Vater Frist bis 30. Juni 2019 setzte, um die Kinder selber zurückzubringen oder durch die Mutter zurückführen zu lassen; im Übrigen regelte es die Modalitäten einer zwangsweisen Rückführung durch die Aufsichtsbehörde KESB als kantonale Vollzugsbehörde.
C.
Gegen dieses Urteil hat der Vater am 27. Mai 2019 beim Bundesgericht eine Beschwerde eingereicht mit den Begehren um dessen Aufhebung und Abweisung des Rückführungsgesuches, eventualiter um Rückweisung der Sache an das Obergericht. Mit Vernehmlassung vom 11. Juni 2019 hat die Mutter auf Abweisung der Beschwerde geschlossen, während die Kindesvertreterin mit Vernehmlassung gleichen Datums die Gutheissung der Beschwerde des Vaters verlangt. Mit Verfügung vom 21. Juni 2019 wurde der Beschwerde die aufschiebende Wirkung erteilt. Mit Replik vom 1. Juli 2019 hielt der Vater an seinen Begehren fest und beantragte die Abweisung der vernehmlassungsweise gestellten Massnahmebegehren der Mutter.
D.
Überdies hat auch die Kindesvertreterin eine Beschwerde gegen das obergerichtliche Urteil erhoben, welche Gegenstand des parallelen Verfahrens 5A_439/2019 bildet.

Erwägungen:
1.
Bei Rückführungsentscheiden nach dem Haager Übereinkommen über die zivilrechtlichen Aspekte internationaler Kindesentführung (HKÜ, SR 0.211.230.02) geht es um die Regelung der Rechtshilfe zwischen den Vertragsstaaten (<ref-ruling> E. 2b S. 224), die in unmittelbarem Zusammenhang mit der Respektierung und Durchsetzung ausländischen Zivilrechts steht (Art. 72 Abs. 2 lit. b Ziff. 1 BGG; <ref-ruling>). Gegen den Entscheid des Kantonsgerichts, welches als einzige kantonale Instanz entschieden hat (Art. 7 Abs. 1 des Bundesgesetzes über internationale Kindesentführung und die Haager Übereinkommen zum Schutz von Kindern und Erwachsenen, BG-KKE, SR 211.222.32), steht die Beschwerde in Zivilsachen offen.
Mit der Beschwerde kann in erster Linie die Verletzung von Bundesrecht (<ref-law>) und von Völkerrecht (<ref-law>) gerügt werden, wozu als Staatsvertrag auch das Entführungsübereinkommen gehört. Das Bundesgericht behandelt aber auch im Anwendungsbereich von <ref-law> nur thematisierte Rechtsfragen; es gelten die Begründungsanforderungen gemäss <ref-law>, welche eine Auseinandersetzung mit den Erwägungen des angefochtenen Entscheides verlangen (<ref-ruling> E. 2 S. 116).
Der kantonal festgestellte Sachverhalt ist für das Bundesgericht grundsätzlich verbindlich (<ref-law>). Es kann höchstens eine offensichtlich unrichtige, d.h. willkürliche Sachverhaltsfeststellung gerügt werden, wobei das strenge Rügeprinzip gilt (Art. 97 Abs. 1 und Art. 106 Abs. 2 BGG). Das Bundesgericht prüft in diesem Fall nur klar und detailliert erhobene und soweit möglich belegte Willkür- und andere Verfassungsrügen, während es auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht eintritt; ausserdem ist aufzuzeigen, inwiefern die Behebung der aufgezeigten Mängel für den Ausgang des Verfahrens entscheidend sein kann (<ref-ruling> E. 2.3 S. 266).
2.
Das Obergericht ist von einem gemeinsamen Sorgerecht der Eltern und von einer widerrechtlichen Verletzung des mütterlichen Sorgerechts im Sinn von Art. 3 HKÜ ausgegangen. Es hat festgestellt, dass der Vater zwar beim Amtsgericht Tetovo in Mazedonien am 25. Februar 2019 ein Scheidungsurteil erwirkt habe, in welchem ihm die Kinder zur weiteren Obhut und Erziehung zugewiesen worden seien, dass aber die Mutter - was aus der Übersetzung des Urteils klar hervorgehe - vom Scheidungsverfahren keine Kenntnis gehabt habe und das Urteil deshalb vom Bezirksgericht U._, wo das Scheidungs- und Obsorgeverfahren hängig sei, nicht anerkannt worden sei und es gemäss <ref-law> auch in der Schweiz nicht anerkannt werden könnte. Im Übrigen würde aber selbst eine Anerkennung des Urteils nichts ändern, weil die Eltern im Zeitpunkt des Verbringens der Kinder in die Schweiz unbestrittenermassen noch verheiratet gewesen seien. Weiter ist das Obergericht davon ausgegangen, dass die Mutter nicht einfach die Kinder in Österreich zurückliess, als sie bei ihren Brüdern in Florenz Hilfe suchte, sondern dass sie das Sorgerecht über die Kinder im Zeitpunkt des Verbringens tatsächlich ausübte. Es hat in diesem Zusammenhang festgestellt, dass keine Anhaltspunkte für die Richtigkeit der anlässlich der Anhörung gemachten Behauptung des Vaters bestünden, wonach die Mutter fremd gegangen sei und ein neues Leben gesucht habe; vielmehr stimme die Darstellung der Mutter, wonach sie die Grosseltern gebeten habe, während ihrer Abwesenheit auf die Kinder aufzupassen, mit den Schilderungen des Vaters in der Vernehmlassung zum Rückführungsgesuch überein. Wie der Mail-Verkehr mit dem Bundesamt für Justiz zeige, habe sie im Anschluss auch hartnäckig versucht, die Kinder in der Schweiz ausfindig zu machen. Dass die Kinder von der Polizei weder am Tag noch in der Nacht am Wohnort des Vaters hätten aufgefunden werden können, begründe den Verdacht, dass sie versteckt worden seien. Jedenfalls fehle es an jeglichen plausiblen Indizien für die Behauptung des Vaters, die Mutter habe das Sorgerecht nicht ausgeübt oder zumindest das Verbringen der Kinder nachträglich genehmigt.
Sodann hat das Obergericht eine mit der Rückführung der Kinder verbundene schwerwiegende Gefahr verneint. A._ sei erst seit kurzem in der Schweiz eingeschult (offenbar seit 8. April 2019) und B._ noch sehr klein. Von einem Einleben in der Schweiz könne keine Rede sein, zumal die Tatsache, dass die Kinder von der Polizei nicht hätten angetroffen werden können, dafür spreche, dass ihre Kontakte nicht über den engsten Familienkreis hinausreichten. Sodann sei nicht ersichtlich, inwiefern die Mutter nicht in der Lage wäre, dem Kindeswohl entsprechend zu handeln. Bei einem Treffen zwischen der Mutter und den Kindern bei der Kindesvertreterin habe die ältere Tochter A._ die Mutter zwar abgelehnt. Das Verhalten des achtjährigen Mädchens sei aber gut nachvollziehbar. Es habe das Gefühl, die Mutter hätte die Kinder damals verlassen, und aufgrund der Parteibefragung sei auch die Annahme naheliegend, dass der Vater es in diesem Gefühl bestärke (er gab zu Protokoll, mit A._ über die Mutter zu sprechen). Analoges ergebe sich aus den Äusserungen des Kindes gegenüber der Kindesvertreterin, wonach die Mutter eine Affäre habe und unverzeihliche Fehler begangen habe. Entgegen der Ansicht der Kindesvertreterin seien diese Aussagen offensichtlich drittbeeinflusst. Dass schliesslich die Mutter seit dem Verbringen der Kinder keinerlei Kontakte zu diesen habe aufnehmen können, sei nicht ihr anzulasten, denn die Kinder seien trotz intensiver Suchbemühungen schlicht nicht lokalisierbar gewesen. Die Vorbringen, die Kinder hätten in der Schweiz eine bessere Zukunft als in Österreich und er selbst stehe finanziell besser da als die Mutter, begründeten keine Gefahren im Sinn des Übereinkommens; solche Überlegungen seien vielmehr im Obsorgeverfahren relevant, welches vor dem Bezirksgericht U._ hängig sei. Im Übrigen habe die Mutter in Österreich eine Arbeitsstelle und eine Wohnung. Sie beabsichtige, ihr Arbeitspensum nach einer Rückkehr der Mädchen zu reduzieren und zähle dabei auf die Unterstützung durch ihre Eltern. Insgesamt präsentiere sich die finanzielle und soziale Situation in Österreich nicht wesentlich anders als in der Schweiz.
3.
Die Ausführungen in der Beschwerde betreffen fast ausschliesslich den Sachverhalt, ohne dass diesbezüglich aber substanziierte Willkürrügen erhoben oder andere Verfassungsverletzungen geltend gemacht würden. Der Beschwerdeführer erwähnt zwar an einer Stelle, dass die offensichtlich unrichtige Sachverhaltsfeststellung im Sinn von <ref-law> mit dem Willkürbegriff übereinstimme (Beschwerde, S. 20). Die Ausführungen bleiben aber - mit einer Ausnahme (dazu E. 3.1) - rein appellatorisch, indem der Beschwerdeführer einfach seine Sicht der Dinge schildert. Insbesondere nimmt er Anstoss daran, dass gemäss dem Obergericht die finanzielle und soziale Situation auf beiden Seiten ähnlich aussehen soll; er ist der Überzeugung, dass es die Kinder bei ihm umfassend gut hätten und ein bewährtes Betreuungskonzept vorliege, während die Situation bei der Mutter prekär sei und es sich bei den mütterlichen Aussagen anlässlich der Anhörung, sie würde ihr Arbeitspensum reduzieren und im Übrigen könnten ihre Eltern (Grosseltern mütterlicherseits) sie bei der Kinderbetreuung unterstützen, um blosse Ausführungen zur Zukunft handle, welche nicht bewiesen seien.
3.1. Die gegen Schluss der Beschwerde sinngemäss angesprochene Frage, ob die Mutter im Zeitpunkt des Verbringens der Kinder das Sorgerecht tatsächlich ausgeübt hat, betrifft Art. 3 Abs. 1 lit. b HKÜ und damit die Widerrechtlichkeit der Sorgerechtsverletzung, von welcher der Beschwerdeführer eingangs der Beschwerde festhält, sie könne offen gelassen werden, weil die Rückführung jedenfalls eine schwerwiegende Gefahr bedeuten würde; insofern ist die Beschwerde widersprüchlich. Indem im Zusammenhang mit Art. 3 Abs. 1 lit. b HKÜ keine Rechtsverletzung geltend gemacht, ja diese Norm nicht einmal genannt wird, zielt die diesbezügliche Sachverhaltskritik - welche als einzige mit einer genügend substanziierten Willkürrüge vorgebracht wird - ins Leere. Darauf wäre folglich nicht einzutreten. Aufgrund der zentralen Bedeutung der widerrechtlichen Sorgerechtsverletzung als unabdingbare Rückführungsvoraussetzung wird dennoch zur Sachverhaltsrüge Stellung genommen und im Anschluss dargelegt, dass nicht von einer fehlenden Sorgerechtsausübung im Sinn von Art. 3 Abs. 1 lit. b HKÜ auszugehen ist:
In tatsächlicher Hinsicht bringt der Beschwerdeführer vor, seine Aussage in der Vernehmlassung, wonach die Mutter die Grosseltern gebeten habe, auf die Kinder aufzupassen, sei insofern willkürlich ausgelegt worden, als das Obergericht daraus natürlich nicht auf ein Einverständnis zu einer Abwesenheit von einer Woche und auch nicht darauf habe schliessen dürfen, dass die Mutter die Kinder nicht im Stich gelassen habe.
Die Umstände, unter welchen die Mutter die Kinder den Grosseltern anvertraute oder sie eben einfach so zurückliess, sowie die Begebenheiten während der Zeit der Abwesenheit von einer Woche werden von den Parteien sehr unterschiedlich dargestellt: Der Vater gab bei der obergerichtlichen Anhörung zu Protokoll, seine Mutter (Grossmutter väterlicherseits) habe ihn angerufen, die Kindsmutter sei weggegangen. Er habe versucht, sie zu erreichen, aber sie habe das Handy ausgeschaltet gehabt, worauf er beim Spital und am Bahnhof U._ angerufen habe. Um Mitternacht habe sie ihm ein SMS geschickt, wonach sie mit einem Liebhaber nach Italien gereist sei. Er sei dann am 28. Juli 2018 nach Österreich gefahren und von dort mit seiner Mutter (Grossmutter väterlicherseits) und den Kindern nach Florenz, um die Kindsmutter zu suchen. Diese habe die ganze Zeit über das Handy ausgeschaltet gehabt. Als er mit den Kindern schon in der Schweiz gewesen sei, habe die Kindsmutter über das Handy geortet werden können. Seine Schwester sei dann hingegangen und habe die Kindsmutter in der Wohnung eines Liebhabers vorgefunden, wobei dieser oben ohne gewesen sei, während sie einen Minijupe getragen habe. Er habe dann aufgrund der Handyortung die Polizei angerufen. Diese habe die Kindsmutter gefragt, ob sie zu Mann und Kindern zurückwolle, worauf sie geantwortet habe, sie fühle sich wohl hier und wolle beim anderen Mann bleiben. Er habe dann die Kinder in der Schweiz angemeldet. Demgegenüber gab die Mutter bei der obergerichtlichen Anhörung zu Protokoll, infolge eines Autounfalles sei die Polizei zuhause vorbeigekommen und habe bei dieser Gelegenheit festgestellt, dass sie und die Kinder nicht gemeldet seien. Sie habe die ganze Geschichte erzählt, wie das gekommen sei. Sie hätten ihr vier Wochen Zeit gegeben, die Sache zu regeln, und sie wäre andernfalls ausgewiesen worden. Es sei ihr schlecht gegangen und sie habe nicht gewusst wohin. Sie habe es schliesslich nicht mehr ausgehalten und alle Arbeitskollegen um Hilfe für eine Wohnung gebeten. Ab 21. Juli 2018 habe sie Urlaub eingegeben. Mit dem Beschwerdeführer habe sie sich nicht besprechen können und deshalb die Situation mit ihren Brüdern besprechen wollen. Gleichentags habe sie den Zug nach Salzburg und von dort nach Florenz genommen. Unterdessen hätten die Schwiegereltern zu den Kindern geschaut; das sei so abgesprochen gewesen. Ihr Bruder in Italien habe ihr geraten, dass sie mit seiner Frau und den Kindern Urlaub in Mazedonien mache, um dort etwas Ruhe zu finden. Sie habe dann die Schwiegermutter angerufen und gesagt, sie werde die Kinder holen, um mit ihnen Ferien in Mazedonien zu verbringen. Die Schwiegermutter habe ihr gesagt, das seien jetzt ihre Kinder und die Kinder ihres Sohnes; sie (Grossmutter) werde sich jetzt um die Kinder kümmern und sie (Kindsmutter) werde diese nicht mehr finden. Darauf sei sie am 28. Juli 2018 nach Österreich zurückgekehrt und habe in Linz ihre Cousine geholt. Am 29. Juli 2018 seien sie gemeinsam zu den Schwiegereltern gefahren und dort sei niemand anzutreffen gewesen.
Die zitierten und weiteren Ausführungen des Vaters anlässlich der obergerichtlichen Anhörung scheinen in vielen Punkten unplausibel und teilweise gerade frei erfunden (beispielsweise, dass er in Florenz die Brüder der Kindsmutter angetroffen habe und diese ihm, nachdem sie gesehen hätten, dass er seriös sei, gesagt hätten, nimm die Kinder, leb dein Leben und lass unsere Schwester, weil sie nicht für die Familie ist, vgl. obergerichtliche Anhörung, S. 2 Z. 26 f.; ebenso die Geschichte mit den angeblichen Äusserungen der Mutter gegenüber der Polizei, wonach sie die Kinder verlassen habe und bei einem Liebhaber leben wolle, vgl. obergerichtliche Anhörung, S. 2 Z. 35 ff., wofür im Übrigen keinerlei Belege eingereicht wurden, obwohl es solche geben müsste). Nachweislich falsch ist sodann die Aussage, er habe sofort nach Ankunft in der Schweiz die Kinder angemeldet; dies war erst am 21. März 2019 der Fall, nachdem diese an seinem Wohnort endlich hatten lokalisiert werden können. Darauf angesprochen, erklärte er die fehlende Anmeldung und die unterbliebene Einschulung der älteren Tochter damit, dass man ihm gesagt habe, ohne Scheidungsabschluss könne man nichts machen (obergerichtliche Anhörung, S. 2 Z. 39 ff.). Ähnlich argumentierte er übrigens bei der Anhörung im Obsorgeverfahren vor dem Bezirksgericht U._ vom 15. März 2019: Die Anmeldung habe nicht erfolgen können, weil beim mazedonischen Scheidungsurteil verschiedene Punkte nicht gepasst hätten; er habe dies gemerkt und das Urteil zur Behebung der Fehler nach Mazedonien zurückschicken müssen (Anhörung Bezirksgericht U._, S. 2 unten). Es bedarf jedoch keiner weiteren Erläuterungen, dass weder die Meldung bei der Einwohnerkontrolle noch die Einschulung eines längst schulpflichtigen Kindes von einem Scheidungstitel abhängig ist. Auffallend ist ferner, dass auch viele weitere Angaben bei der Anhörung vor dem Bezirksgericht U._ widersprüchlich und unrealistisch waren und er auf zahlreiche Fragen bezüglich seines Verhaltens gegenüber der Kindsmutter im Zusammenhang und im Anschluss an das Verbringen der Kinder entweder keine Antworten gab oder aber solche, welche keinen Bezug zur Frage hatten. Demgegenüber sind die Aussagen der Mutter, wie dies schon das Obergericht festhielt, nachvollziehbar und von der Abfolge her logisch; ferner hat sie das Geschehen und dessen Ablauf vor dem Bezirksgericht U._ im Wesentlichen gleich geschildert wie vor dem Obergericht.
Zu prüfen ist im Folgenden, ob die Umstände dafür sprechen, dass die Mutter im Zeitpunkt des Verbringens der Kinder durch den Vater das ihr zustehende Sorgerecht im Sinn von Art. 3 Abs. 1 lit. b HKÜ nicht ausgeübt hat.
Art. 3 Abs. 1 lit. b HKÜ ist im Zusammenhang mit dem Grundanliegen des Übereinkommens zu lesen, den Status quo ante wieder herzustellen; verbrachte Kinder sollen nicht zu einem Elternteil zurückgeführt werden, welcher sich erst nach dem Verbringen auf sein Sorgerecht besinnt und vorher gar keine Bindung zu seinen Kindern hatte (PIRRUNG, in: Staudingers Kommentar zum BGB, Vorbem C-H zu Art. 19 EGBGB, Berlin 2009, D 32; SIEHR/MARKUS, in: Zürcher Kommentar, <ref-law> Anhang I, Art. 3 HKÜ, N. 27; MAZENAUER, Internationale Kindesentführungen und Rückführungen - Eine Analyse im Lichte des Kindeswohls, Diss. Freiburg 2012, Rz. 34 und 207). In diesem Sinn sind keine hohen Anforderungen an die tatsächliche Ausübung des Sorgerechtes zu stellen; vielmehr besteht eine Vermutung, dass der Sorgerechtsinhaber seine Rechte und Pflichten auch tatsächlich wahrgenommen hat (PIRRUNG, a.a.O., D 32; MAZENAUER, a.a.O., Rz. 208). Für die Annahme des Gegenteils müsste erwiesen sein, dass sich der Elternteil überhaupt nicht um die Kinder gekümmert und das Sorgerechtes definitiv aufgegeben hat (<ref-ruling> E. 2.2.1 S. 669 m.w.H.).
Vorliegend lebten die Kinder in Österreich im Haushalt der Mutter, wobei diese zufolge Aufgabe der Familienwohnung schliesslich zu den Grosseltern väterlicherseits ziehen musste. Es bestehen keinerlei Indizien, dass die Mutter, als sie in Florenz bei ihren Brüdern Hilfe holen wollte, das Sorgerecht in einer Weise hätte aufgeben wollen oder tatsächlich aufgegeben hätte, dass im Zeitpunkt des wenige Tage später erfolgten Verbringens durch den Vater von einer Nichtausübung des mütterlichen Sorgerechtes im Sinn von Art. 3 Abs. 1 lit. b HKÜ zu sprechen wäre. Die Kinder verblieben bei den Grosseltern in der Wohnung, in welcher sie sich mit der Mutter seit mehreren Monaten aufhielten. Es ist zwar umstritten, aber aufgrund ihres vorangehenden und nachfolgenden Verhaltens wahrscheinlich, dass die Mutter die Kinder den Grosseltern für die Zeit der Abwesenheit anvertraut hat. Dabei handelt es sich notabene um die Grossmutter, welche nunmehr im väterlichen Haushalt in der Schweiz lebt und von welcher der Vater im Zusammenhang mit dem behaupteten Einleben der Kinder in der Schweiz (dazu E. 3.2) ausführlich berichtet, wie sie diese fürsorglich betreue und seit deren Geburt bei Verhinderungen stets als Betreuerineingesprungen sei. Vor diesem Hintergrund bleibt der mehr oder weniger offen erhobene Vorwurf, die Mutter habe die Kinder einfach im Stich gelassen und ein neues Leben beginnen wollen, ohne greifbare Grundlage. Sie kehrte nach einer Woche zurück und traf die Situation an, dass die Kinder zwischenzeitlich verbracht worden waren. Sie begab sich umgehend zur Polizei und wandte sich wenige Tage später auch an das Gericht. Sodann stellte sie bereits nach einem Monat einen Rückführungsantrag, wobei sich das Verfahren vor der schweizerischen Zentralbehörde in der Folge in die Länge zog, weil die Kinder am Wohnsitz des Vaters trotz umfangreicher polizeilicher Ermittlungen bis gegen Ende März 2019 nicht aufgefunden werden konnten. Es kann deshalb keine Rede davon sein, dass die Mutter im Zeitpunkt des Verbringens das Sorgerecht im Sinn von Art. 3 Abs. 1 lit. b HKÜ erwiesenermassen nicht ausgeübt hätte.
3.2. Soweit der Beschwerdeführer dafür hält, bei ihm habe sich die Betreuung aufgrund eines klaren Betreuungskonzeptes seit fast einem Jahr bewährt und die Kinder seien in der Schweiz bestens integriert, spricht er sinngemäss das Einleben im Sinn von Art. 12 Abs. 2 HKÜ an. Wie das Obergericht zutreffend festgehalten hat, kann dieses aber nur dann geprüft werden, wenn zwischen dem widerrechtlichen Verbringen und dem Rückführungsantrag mehr als ein Jahr verstrichen ist, was vorliegend nicht zutrifft.
Nur der Vollständigkeit halber sei festgehalten, dass sich die Situation in der Schweiz keineswegs so ideal präsentiert wie vom Vater dargestellt: Fakt ist, dass er die Kinder während des ganzen Herbstes und Winters in der Schweiz nicht angemeldet und die ältere Tochter, die klarerweise in schulpflichtigem Alter war, nicht eingeschult hat. Sodann hat er ab Ende August 2018 konsequent jeglichen telefonischen bzw. per Skype erfolgenden Kontakt zwischen der älteren Tochter und der Mutter unterbunden, was von einer fehlenden Bindungstoleranz zeugt. Im Übrigen hat er A._ offensichtlich auch in manipulativer Weise eingeflösst, die Mutter habe sie im Stich gelassen und durch Fremdbeziehungen schwere Verfehlungen begangen. Er hat denn auch eingeräumt, dass er mit A._ über die Mutter spreche (obergerichtliche Anhörung, S. 4, Z. 18), und anders lässt sich die heute erfolgende Ablehnung der Mutter und die moralisch-herabsetzenden Äusserungen zu offensichtlich elternbezogenen Themenkreisen, welche für ein achtjähriges Kind nicht altersentsprechend sind, nicht erklären (von der Kindesvertreterin in der erstinstanzlichen Vernehmlassung dahingehend geschildete Äusserungen von A._, wonach die Mutter schwere Verfehlungen begangen habe, indem sie ständig Einkäufe vorgegeben und dann immer zu anderen Männern gegangen sei und indem ihr einmal im Park ein fremder Mann Kaffee gebracht habe).
Hintergrund, dass der Vater die ältere Tochter bewusst oder unbewusst in den elterlichen Beziehungskonflikt einbezieht, scheint sein gekränkter Stolz als Familienhaupt zu sein. In der Anhörung vor dem Obergericht und dem Bezirksgericht U._ tritt die Haltung zutage, wonach er "Mann des Hauses" ist (obergerichtliche Anhörung, S. 2 Z. 6) und dass er sich schämen würde, nach Österreich zurückzugehen, weil sie so unmoralische Sachen gemacht habe (obergerichtliche Anhörung, S. 3 Z. 24); die Mutter habe kein Recht auf Kontakt mit den Kindern mehr (vgl. obergerichtliche Anhörung, S. 4 Z. 12 f.) und er könnte nicht dulden, dass die Kinder bei ihr und ihrem Liebhaber leben würden (Anhörung Bezirksgericht U._, S. 5 oben). Offenbar wird der Vater bei seiner Überzeugung, wonach die Mutter fremd gegangen sei - was eine blosse Behauptung, in Bezug auf die Frage der Kindesrückführung aber ohnehin irrelevant ist - und sie deshalb die Rechte auf die Kinder verwirkt habe, von seinem Umfeld getragen. Jedenfalls scheinen im betreffenden Kontext die Ausführungen der Mutter vor dem Bezirksgericht U._ plausibel, wonach bei einem Telefonat mit dem Beschwerdeführer Ende August 2018 auch dessen Schwester anwesend gewesen sei. Diese und die Schwiegermutter hätten sie unter der Gürtellinie als Hure beschimpft und ihr mitgeteilt, dass sie die Kinder nie mehr sehen werde. Seither habe sie keinerlei Kontakt zur älteren Tochter mehr haben können. Vorher, d.h. während des Monats August 2018 habe sie mit A._ hin und wieder skypen können, wobei sie den Eindruck gehabt habe, dass A._ verängstig und die Grossmutter im Hintergrund gewesen sei. A._ habe ihr gesagt, dass sie und B._ beim Vater in der Schweiz seien, aber ihr keine Adresse bekanntgegeben (Anhörung Bezirksgericht U._, S. 8).
3.3. Als Zwischenergebnis ist somit festzuhalten, dass eine widerrechtliche Sorgerechtsverletzung im Sinn von Art. 3 HKÜ vorliegt und als Folge die Kinder in den Staat zurückzuführen sind, in welchem sie vor dem Verbringen ihren gewöhnlichen Aufenthalt hatten (Art. 12 Abs. 1 HKÜ), soweit nicht Ausschlussgründe nachgewiesen sind.
3.4. Als Ausschlussgrund wird, was denn auch den Schwerpunkt der Beschwerde bildet, eine schwerwiegende Gefahr im Sinn von Art. 13 Abs. 1 lit. b HKÜ behauptet, wobei keine rechtlichen Ausführungen, sondern Sachverhaltsbehauptungen erfolgen. Diese werden jedoch nicht in Form von substanziierten Willkürrügen, sondern in appellatorischer Weise vorgetragen. Aber selbst bei korrekten Rügen wäre nicht ansatzweise eine schwerwiegende Gefahr im Sinn von Art. 13 Abs. 1 lit. b HKÜ erkennbar:
Nach der konstanten und in verschiedenen Entscheiden (namentlich Urteile 5A_913/2010 vom 4. Februar 2011 E. 5.1 und 5A_840/2011 vom 13. Januar 2012 E. 3.1, je mit zahlreichen Hinweisen) zusammengefassten bundesgerichtlichen Rechtsprechung liegt eine schwerwiegende Gefahr körperlicher oder seelischer Schädigung im Sinn von Art. 13 Abs. 1 lit. b HKÜ zum Beispiel bei einer Rückführung in ein Kriegs- oder Seuchengebiet vor, aber auch, wenn ernsthaft zu befürchten ist, dass das Kind nach der Rückgabe misshandelt oder missbraucht wird und nicht zu erwarten ist, dass die zuständigen Behörden des Herkunftsstaates gegen die Gefährdung erfolgreich einschreiten. Keine schwerwiegende Gefahr seelischer Schädigung begründen anfängliche Sprach- und Reintegrationsschwierigkeiten, wie sie sich bei Kindern ab einem gewissen Alter mehr oder weniger zwangsläufig ergeben. Sodann geht es im Rückführungsverfahren nicht um materiell-rechtliche Fragen, wie sie für die Zuteilung des Sorgerechts massgebend sind, namentlich bei welchem Elternteil oder in welchem Land das Kind besser aufgehoben oder welcher Elternteil zur Erziehung und Betreuung besser geeignet wäre; der Entscheid darüber ist nach dem System des HKÜ dem Sachrichter des Herkunftsstaates vorbehalten (vgl. Art. 16 und 19 HKÜ). Was das Zusammenspiel zwischen Grundsatz und Ausnahme anbelangt, besteht in der Rechtsprechung ein allgemeiner Konsens, wonach die Ausschlussgründe eng auszulegen und bei Art. 13 Abs. 1 lit. b HKÜ nur wirkliche Gefahren zu berücksichtigen sind.
Vorliegend steht fest, dass der Vater zur Zeit des erstinstanzlichen Verfahrens arbeitslos war und bei der Anhörung am 30. April 2019 ausführte, momentan möchte er nicht arbeiten, sondern seine Zeit den Kindern widmen. Vor Bundesgericht bringt er - was an sich ein unzulässiges Novum ist (<ref-law>) - vor, er werde eine neue Anstellung im Geschäft einer Cousine antreten. Seine Mutter (Grossmutter väterlicherseits) zog im Sommer 2018 in seinen Haushalt in der Schweiz und betreut während arbeitsbedingten Abwesenheiten die Kinder, während sein Vater (Grossvater väterlicherseits) in Österreich verblieben ist, aber ab und zu auf Besuch kommt und offenbar plant, ebenfalls in die Schweiz zu kommen. Auf der anderen Seite geht die Kindsmutter in Österreich momentan einem Vollzeiterwerb nach. Ab der Rückführung der Kinder will sie auf eine Teilzeitarbeit wechseln, wobei nach ihren Aussagen bei der obergerichtlichen Anhörung ihre Eltern (Grosseltern mütterlicherseits), welche 58- bzw. 60-jährig sind und keiner Erwerbstätigkeit mehr nachgehen, Unterstützung bei der Kinderbetreuung zugesichert haben.
Zumal der Vater bei einer Rückführung der Kinder diesen gegenüber unterhaltspflichtig wäre, ist nicht zu sehen und schon gar nicht dargetan, inwiefern die finanzielle Situation, wenn die Kinder weiterhin bei ihm leben, massgeblich besser und es jedenfalls bei einer Rückkehr zur Mutter so sein soll, dass für die Kinder schwerwiegende Gefahren drohen würden. Ebenso wenig lassen sich solche in Bezug auf die zukünftige Betreuungssituation in Österreich ausmachen. In diesem Zusammenhang verkennt der Beschwerdeführer mit seinem Hauptvorwurf, die genauen Verhältnisse in Österreich seien vom Obergericht zu wenig abgeklärt und seitens der Mutter nicht mit stringenten Beweisen "untermauert", dass die Situation, welche Kinder bei einer Rückführung zu erwarten haben, immer eine zukünftige ist und sich die Zukunft per definitionem nicht in einem strikten Sinn beweisen lässt. Insbesondere kann von der Mutter nicht verlangt werden, zumal die finanziellen Mittel der Familie insgesamt sehr beschränkt sind, dass sie bereits auf Vorrat auf eine Teilzeitarbeit hätte wechseln und ihre eigenen Eltern in die Nähe holen müssen, damit überhaupt eine Rückführung ins Auge gefasst werden könnte. Im Übrigen sind die Kinder in einem Alter, in welchem sie sich in Österreich rasch wieder einleben können. Sie würden auch in der gleichen Sprache beschult und es ist nicht erkennbar, inwiefern ihnen dort insgesamt eine Zukunft bevorstehen soll, welche schwerwiegende Gefahren im Sinn der Rechtsprechung zu Art. 13 Abs. 1 lit. b HKÜ mit sich bringen könnte. Insbesondere ist auch nicht zu sehen, dass die dortige Wohnung aufgrund der Grösse von 56 m2 eine schwerwiegende Gefahr für die Kinder darstellen soll, welche einer Rückführung entgegensteht.
3.5. Insgesamt ist festzuhalten, dass mit der Rückführung an den früheren Verhältnissen angeknüpft wird. Der Vater hat seinerzeit in der Schweiz eine Erwerbsarbeit aufgenommen und die Kinder sind bei der Mutter in Österreich verblieben. Aufgrund fehlender finanzieller Möglichkeiten mussten sie sich in der Folge vorübergehend bei den Grosseltern väterlicherseits einquartieren. Die Kinder standen damit aber nach wie vor in mütterlicher Obhut und in einem gelebten gemeinsamen Haushalt mit ihr, aus welchem sie der Vater, welcher längst einen eigenen Haushalt im Ausland begründet hatte, verbrachte, als die Mutter für einige Tage abwesend war. Nunmehr werden die Kinder in den mütterlichen Haushalt zurückgeführt, welcher sich im 15 km von U._ entfernten V._ befindet, wobei die Mutter über eine Arbeit und eine Wohnung verfügt und ihr die Eltern (Grosseltern mütterlicherseits) Unterstützung bei der Kinderbetreuung zugesagt haben.
4.
Das Obergericht hat dem Beschwerdeführer eine Frist zur freiwilligen Rückführung gesetzt und das Bundesgericht pflegt dies normalerweise auch zu tun, wobei die Frist vorliegend zufolge der gewährten aufschiebenden Wirkung neu anzusetzen wäre.
Indes besteht angesichts der konkreten heutigen Umstände (unklare Arbeitssituation des Vaters; unklare Aufenthaltssituation, indem gemäss Aktennotiz des Obergerichts die Grossmutter väterlicherseits nach wie vor nicht gemeldet und der Ausländerausweis des Vaters abgelaufen ist; Hinterlegung einzig der slowakischen Pässe der Kinder, während angeblich keine mazedonischen Ausweispapiere bestehen sollen und den kantonalen Behörden die Herstellung eines Kontaktes mit der mazedonischen Botschaft bisher nicht gelungen ist) sowie angesichts des bisherigen, ausgeprägt eigenmächtigen Verhaltens des Vaters und schliesslich angesichts seiner Überzeugung, die Mutter habe keinerlei Rechte mehr auf die Kinder, die konkrete Befürchtung, dass der Vater eine Frist zur freiwilligen Rückführung zu einem Untertauchen bzw. zu einem Absetzen nach Mazedonien nutzen könnte, zumal für die eingeschulte ältere Tochter ab dem 6. Juli 2019 die Sommerferien beginnen. Es drängt sich aus diesen Gründen und überdies angesichts der vollständigen elterlichen Kommunikationsblockade auf, eine behördenbegleitete Übergabe der Kinder in den Räumlichkeiten der kantonalen Vollzugsbehörde zu organisieren, wie die Mutter dies vernehmlassungsweise verlangt, wobei entsprechend dem für diesen Fall gemachten Postulat der Kindesvertreterin vorab eine kinderpsychologisch begleitete Kontaktherstellung und Wiederannäherung insbesondere mit der älteren, der Mutter entfremdeten Tochter A._ stattzufinden hat (vgl. dazu die Ausführungen im parallelen Urteil 5A_339/2019 E. 4.5).
Gestützt auf Art. 6 Abs. 1 und Art. 11 Abs. 1 BG-KKE ist der Vollzug der Rückführung mithin wie folgt zu regeln:
Der Vater hat sich ab Donnerstag, 4. Juli 2019, täglich bei der Kantonspolizei Solothurn, Regionenposten W._, zu melden, und zwar an den Wochentagen und am Samstagvormittag physisch sowie am Sonntag telefonisch unter einer von der Kantonspolizei noch zu bezeichnenden Nummer, unter Androhung der Straffolgen von <ref-law> und der sofortigen Fremdplatzierung der Kinder im Unterlassungsfall. Soweit der Vater inzwischen wieder arbeiten sollte, kann die tägliche Meldung nach Rücksprache mit dem Amt für soziale Sicherheit auch auf einem anderen Polizeiposten stattfinden.
Die Kantonspolizei Solothurn, Regionenposten W._, ist anzuweisen, das Amt für soziale Sicherheit, Aufsichtsbehörde KESB, sofort in Kenntnis zu setzen, wenn die tägliche Meldung des Vaters ausbleiben sollte.
Das Amt für soziale Sicherheit des Kantons Solothurn, Aufsichtsbehörde KESB, als kantonale Vollzugsbehörde ist zu beauftragen, mit der Mutter betreffend Anreise in die Schweiz und gegebenenfalls Unterbringung Kontakt aufzunehmen, unter Betrauung eines entsprechenden Dienstes bzw. entsprechender Fachpersonen eine kindesgerechte Kontaktaufnahme und Wiederannäherung zwischen den Kindern und der Mutter zu organisieren, bei Kooperationsunwilligkeit des Vaters notfalls durch vorübergehende Platzierung der Kinder in einer Pflegefamilie, und mit den zuständigen Kindesschutzbehörden in Österreich betreffend die Begleitung des Wiedereinlebens durch Fachpersonen Kontakt aufzunehmen, soweit dies noch nicht erfolgt sein sollte.
Die Übergabe der Kinder hat am 12. Juli 2019, 10:00 Uhr, in den Räumlichkeiten des Amtes für soziale Sicherheit des Kantons Solothurn zu erfolgen. Die Vollzugsbehörde ist ermächtigt, hierfür und bei den vorangehenden Vorkehrungen soweit erforderlich polizeiliche Unterstützung in Anspruch zu nehmen.
5.
In Kindesrückführungsverfahren werden keine Gerichtskosten erhoben und die Rechtsvertreter der Beteiligten aus der Gerichtskasse entschädigt (Art. 26 Abs. 2 HKÜ). Die gestellten Gesuche um unentgeltliche Rechtspflege sind deshalb gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Der Beschwerdeführer hat sich ab Donnerstag, 4. Juli 2019, täglich bei der Kantonspolizei Solothurn, Regionenposten W._, zu melden, und zwar an den Wochentagen und am Samstagvormittag physisch sowie am Sonntag telefonisch unter einer mit der Kantonspolizei abzusprechenden Nummer, unter Androhung der Straffolgen von <ref-law> (Wer der von einer zuständigen Behörde oder einem zuständigen Beamten unter Hinweis auf die Strafdrohung dieses Artikels an ihn erlassenen Verfügung nicht Folge leistet, wird mit Busse bestraft) und der sofortigen Fremdplatzierung der Kinder im Unterlassungsfall.
3.
Die Kantonspolizei Solothurn, Regionenposten W._, wird angeweisen, das Amt für soziale Sicherheit, Aufsichtsbehörde KESB, sofort in Kenntnis zu setzen, wenn die tägliche Meldung des Beschwerdeführers ausbleiben sollte.
4.
Das Amt für soziale Sicherheit, Aufsichtsbehörde KESB, des Kantons Solothurn als kantonale Vollzugsbehörde wird beauftragt:
- mit der Mutter betreffend Anreise in die Schweiz und gegebenenfalls Unterbringung Kontakt aufzunehmen,
- unter Betrauung eines entsprechenden Dienstes bzw. entsprechender Fachpersonen eine kindesgerechte Kontaktaufnahme und Wiederannäherung zwischen den Kindern und der Mutter zu organisieren, bei Kooperationsunwilligkeit des Vaters notfalls durch vorübergehende Platzierung der Kinder in einer Pflegefamilie,
- und mit den zuständigen Kindesschutzbehörden in Österreich betreffend die Begleitung des Wiedereinlebens durch Fachpersonen Kontakt aufzunehmen.
5.
Die Übergabe der Kinder findet statt am 12. Juli 2019, 10:00 Uhr, in den Räumlichkeiten des Amtes für soziale Sicherheit des Kantons Solothurn.
Die Vollzugsbehörde ist ermächtigt, hierfür und bei den vorangehenden Vorkehrungen soweit erforderlich polizeiliche Unterstützung in Anspruch zu nehmen.
6.
Es werden keine Gerichtskosten erhoben.
7.
Die Rechtsanwältinnen Gabriela Loepfe-Lazar, Barbara Obrecht Steiner und Dana Matanovic werden aus der Bundesgerichtskasse mit je Fr. 3'000.-- entschädigt.
8.
Dieses Urteil wird den Parteien, der Kindesvertreterin, dem Obergericht des Kantons Solothurn, Zivilkammer, der kantonalen Vollstreckungsbehörde, der Kantonspolizei Solothurn, Regionenposten W._, und dem Bundesamt für Justiz als Zentralbehörde für Kindesentführungen schriftlich mitgeteilt.
Lausanne, 2. Juli 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Möckli