Fatti:
A.
A._ e B._ sono i genitori di C._, D._ e E._ (nati rispettivamente nel 2007, 2009 e 2011). La coppia ha convissuto dal 1999 in Italia, poi brevemente in Austria e dal 2008 in Svizzera: dapprima a X._ (Cantone Zurigo) e dal 2014 ad Y._ (Cantone Ticino). Il 27 giugno 2011 la coppia ha sottoscritto una convenzione, approvata dall'autorità tutoria di X._, secondo cui i genitori detengono congiuntamente l'autorità parentale e, in caso di scioglimento della comunione domestica e di disaccordo fra i genitori, la madre detiene la custodia dei figli.
La coppia si è separata nel luglio 2017 a seguito di un presunto episodio di violenza domestica compiuto da A._. Dal luglio 2017 al giugno 2018 B._ ed i tre figli hanno soggiornato in una struttura protetta. Il procedimento penale a carico di A._ è in seguito stato chiuso con un decreto di abbandono per i reati di lesioni semplici, vie di fatto, minaccia, coazione, coazione sessuale e molestie sessuali e con un decreto di stralcio per il reato di ingiuria.
Nel frattempo, con istanza 9 agosto 2017 B._ ha chiesto l'autorizzazione a trasferirsi in Austria, nella regione di Z._, con i tre figli. Con decisione 27 giugno 2018 l'Autorità regionale di protezione 4 sede di Paradiso ha accolto l'istanza, autorizzando detto trasferimento e regolamentando il diritto di visita del padre
B.
Mediante sentenza 8 novembre 2018 il Presidente della Camera di protezione del Tribunale d'appello del Cantone Ticino ha respinto, nella misura della sua ammissibilità, il reclamo introdotto da A._ avverso la decisione dell'autorità di protezione.
C.
Con ricorso in materia civile 16 novembre 2018, poi completato in data 10 dicembre 2018, A._ ha impugnato la sentenza cantonale dinanzi al Tribunale federale, postulandone in via principale la riforma nel senso che l'autorizzazione al trasferimento dei figli all'estero sia annullata e che la custodia dei minori gli sia affidata (riservato il più ampio diritto di visita alla madre), ed in via subordinata l'annullamento con il rinvio degli atti all'autorità di protezione per ulteriore approfondimento della situazione sociale, famigliare, abitativa e professionale della madre in Austria e per un nuovo ascolto dei minori. Il ricorrente ha inoltre chiesto di essere posto al beneficio dell'assistenza giudiziaria.
Con decreto 7 dicembre 2018 al ricorso è stato conferito l'effetto sospensivo (già concesso in via supercautelare in data 19 novembre 2018). Nella sua presa di posizione a sfavore di tale istanza, anche l'opponente ha chiesto di essere posta al beneficio dell'assistenza giudiziaria.
Non sono state chieste determinazioni nel merito.

Diritto:
1.
1.1. La decisione impugnata è una decisione finale (<ref-law>) che è stata pronunciata su ricorso dall'ultima istanza cantonale (<ref-law>) in una causa civile di natura non pecuniaria (<ref-law>; sentenza 5A_945/2015 del 7 luglio 2016 consid. 1.1, non pubblicato in <ref-ruling>). Il ricorso in materia civile, tempestivo (<ref-law>) ed inoltrato dalla parte soccombente nella sede cantonale che ha un interesse degno di protezione alla modifica della sentenza impugnata (<ref-law>), risulta pertanto in linea di principio ammissibile.
1.2. Il Tribunale federale applica il diritto d'ufficio (<ref-law>). Nondimeno, tenuto conto dell'onere di allegazione e motivazione posto dall'art. 42 cpv. 1 e 2 LTF, la cui mancata ottemperanza conduce all'inammissibilità del gravame, il Tribunale federale esamina di regola solo le censure sollevate (<ref-ruling> consid. 2.4 con rinvii). Il ricorrente deve pertanto spiegare nei motivi del ricorso, in modo conciso e confrontandosi con i considerandi della sentenza impugnata, perché quest'ultima viola il diritto (<ref-ruling> consid. 1.2.2; <ref-ruling> consid. 2.4). Per le violazioni di diritti fondamentali e di disposizioni di diritto cantonale e intercantonale le esigenze di motivazione sono più severe; il ricorrente deve indicare in modo chiaro e dettagliato i diritti che sono stati violati e spiegare in cosa consista la violazione (<ref-law>; <ref-ruling> consid. 1.2.2; <ref-ruling> consid. 2.4).
Il Tribunale federale fonda il suo ragionamento giuridico sull'accertamento dei fatti svolto dall'autorità inferiore (<ref-law>); può scostarsene o completarlo solo se è stato svolto in violazione del diritto ai sensi dell'<ref-law> o in modo manifestamente inesatto (<ref-law>). L'accertamento dei fatti contenuto nella sentenza impugnata può essere censurato alle stesse condizioni; occorre inoltre che l'eliminazione dell'asserito vizio possa influire in maniera determinante sull'esito della causa (<ref-law>). Se rimprovera all'autorità inferiore un accertamento dei fatti manifestamente inesatto - ossia arbitrario (<ref-ruling> consid. 2) - il ricorrente deve sollevare la censura e motivarla in modo preciso, come esige l'<ref-law>.
Non possono essere addotti nuovi fatti o nuovi mezzi di prova, a meno che non ne dia motivo la decisione impugnata (<ref-law>).
2.
2.1. Il figlio è sentito personalmente e in maniera adeguata dall'autorità di protezione dei minori o da un terzo incaricato, eccetto che la sua età o altri motivi gravi vi si oppongano (<ref-law>).
Se il minore è già stato sentito, occorre prescindere da una nuova audizione qualora comporti una sofferenza che non può essere imposta al figlio, ciò che può verificarsi in presenza di un conflitto di lealtà particolarmente grave, e se oltre a ciò si può presumere che non emergeranno nuovi elementi o che l'auspicata utilità di tale ascolto non sia proporzionata con la sofferenza provocata al minore dall'ulteriore audizione. La rinuncia ad una nuova audizione presuppone tuttavia che il minore sia stato interpellato in merito ai punti determinanti per il giudizio e che l'esito dell'ascolto sia ancora attuale (<ref-ruling> consid. 4; sentenza 5A_215/2017 del 25 ottobre 2017 consid. 4.2).
2.2. Il Presidente della Camera di protezione ha accertato che nel caso concreto i figli sono stati sentiti in data 23 ottobre 2017 dal membro permanente dell'Autorità regionale di protezione 4 sede di Paradiso e poi in data 21 febbraio e 2 maggio 2018 dagli operatori dell'Ufficio cantonale dell'aiuto e della protezione (su incarico della predetta autorità). Il Giudice cantonale ha poi ritenuto che il rimprovero del padre mosso all'autorità di prime cure per non aver riascoltato i figli fosse irricevibile, poiché privo di un confronto con la motivazione di tale autorità secondo cui una nuova audizione non risultava né indispensabile né opportuna in considerazione dei precedenti ascolti e del fatto che i minori manifestavano una significativa sofferenza per il forte coinvolgimento nel conflitto genitoriale, e pure infondato, poiché basato su un'errata concezione dell'audizione, volta non a ricercare presso il figlio una determinazione precisa quanto all'esito del procedimento, bensì a permettere al giudice di farsi un'idea personale e di disporre di una fonte di informazioni supplementare per stabilire la fattispecie e prendere una decisione.
2.3. Il ricorrente afferma che il Presidente della Camera di protezione gli avrebbe rimproverato "a torto" di non essersi confrontato con la motivazione dell'autorità di protezione. Sostiene poi che il Giudice cantonale non avrebbe tenuto conto della costanza e dell'insistenza con cui i figli avrebbero riferito di non volere trasferirsi in Austria, ciò che avrebbe dovuto condurre ad un ulteriore ascolto degli stessi per approfondire le ragioni alla base del loro fermo rifiuto e per raccogliere ulteriori elementi ("non di certo per ricercare presso il bambino una determinazione precisa quanto all'esito del procedimento, come sostenuto nella decisione impugnata"), anche alla luce del fatto che i minori sarebbero stati ascoltati solo una volta dall'autorità di protezione, il 23 ottobre 2017, ossia all'inizio della procedura, per cui tale audizione non sarebbe più attuale.
2.4. Il ricorrente non si preoccupa tuttavia di indicare con precisione dove, nel reclamo, si sarebbe misurato con la motivazione contenuta nella decisione di prima istanza, per cui non dimostra che il suo allegato cantonale fosse in realtà ricevibile in merito alla questione del mancato riascolto dei minori. Egli del resto non riesce nemmeno a dimostrare che fosse fondato: l'argomentazione secondo cui i figli non sarebbero stati sentiti su elementi decisivi e l'esito dell'audizione non sarebbe attuale si basa infatti su circostanze che non emergono dall'impugnata sentenza (come il rifiuto dei minori al trasferimento in Austria), rispettivamente che contraddicono l'accertamento ivi contenuto (i figli sono in realtà stati sentiti in tre occasioni, l'ultima volta nel maggio 2018 da un terzo incaricato), senza che siano adempiuti i presupposti che permettono al Tribunale federale di scostarsi dai fatti stabiliti dall'autorità inferiore (v. art. 97 cpv. 1 e 99 cpv. 1 LTF; supra consid. 1.2). In tali condizioni, la critica ricorsuale non è atta a scalfire il giudizio del Presidente della Camera di protezione - in ogni modo conforme alla giurisprudenza del Tribunale federale (v. supra consid. 2.1) - e non merita pertanto accoglimento.
3.
3.1. L'autorità parentale include il diritto di determinare il luogo di dimora del figlio (<ref-law>). Se i genitori esercitano l'autorità parentale congiuntamente, un genitore può trasferire il luogo di dimora del figlio all'estero soltanto con il consenso dell'altro genitore oppure per decisione del giudice o dell'autorità di protezione dei minori (<ref-law>). Se necessario, i genitori si accordano, conformemente al bene del figlio, in merito a una modifica dell'autorità parentale, della custodia, delle relazioni personali e del contributo di mantenimento. Se non raggiungono un accordo, decide il giudice o l'autorità di protezione dei minori (<ref-law>).
La giurisprudenza ha fissato alcuni criteri applicabili alla questione del trasferimento del luogo di dimora del figlio. Nel rispetto delle libertà di domicilio e di movimento dei genitori, i motivi che spingono uno di loro a trasferirsi non sono rilevanti. Non occorre pertanto chiedersi se per il bene del figlio sarebbe preferibile che il genitore non si trasferisse, ma se il bene del figlio è meglio tutelato seguendo il genitore che vuole trasferirsi oppure rimanendo con l'altro genitore, tenendo già conto di eventuali modifiche concernenti la custodia, le relazioni personali ed il contributo di mantenimento fondate sull'<ref-law>. La risposta va data in funzione del bene del figlio e tenendo conto delle circostanze del caso concreto. Il modello di partecipazione alla cura del figlio finora applicato rappresenta il punto di partenza dell'esame. Se entrambi i genitori si occupano in modo paritario del figlio e sono pronti ad occuparsene anche in futuro, la situazione di partenza è neutra e occorre allora ricorrere ad altri criteri per determinare la soluzione che protegga meglio l'interesse del minore, quali la capacità educativa dei genitori, la loro capacità di favorire i contatti tra il figlio e l'altro genitore, l'effettiva possibilità dei genitori di prendersi cura del figlio, la stabilità delle relazioni, la lingua, la scolarizzazione, le necessità mediche, nonché il parere dei figli più grandi. Se invece le cure del figlio sono affidate interamente o in modo preponderante alla persona che si trasferisce, si partirà tendenzialmente dal presupposto che far rimanere il figlio con tale genitore tuteli meglio il suo intesse; un'attribuzione della custodia all'altro genitore (ammesso che egli sia atto e disposto ad accogliere il figlio) comporta un esame accurato, sulla base delle circostanze del caso concreto, della compatibilità con il bene del minore (<ref-ruling> consid. 2.3-2.8; <ref-ruling> consid. 4.4; <ref-ruling> consid. 2.5).
3.2. Il Presidente della Camera di protezione ha osservato che da luglio 2017 i figli sono affidati esclusivamente alla madre in virtù della convenzione 27 giugno 2011 sottoscritta dai genitori (v. supra consid. in fatto A), per cui si può partire dal presupposto che l'interesse dei minori sia meglio tutelato permettendo loro di trasferirsi con lei in Austria. Peraltro, anche ammettendo che di fatto i genitori si occupino invece in maniera paritaria dei figli, come sostenuto dal padre, il trasferimento all'estero con la madre rimane in ogni modo la soluzione più conforme al bene dei figli.
Secondo il Giudice cantonale, infatti, c ontrariamente a quanto fatto valere nel reclamo il trasferimento in Austria non costituirebbe uno sradicamento per i minori: ad Y._ non vi sono particolari radici o legami famigliari (il Comune è stato scelto perché a metà strada tra il luogo di lavoro della madre [Zugo/Zurigo] e del padre [Milano], i figli vi hanno vissuto soltanto per poco più di tre anni ed il parente più prossimo è la nonna paterna a Milano), i figli da sempre parlano tedesco con la madre e con i parenti austriaci e hanno già vissuto in un contesto germanofono. Il progetto di vita in Austria è inoltre stato sufficientemente circostanziato dalla madre, la quale in sede di osservazioni al reclamo ha aggiunto ulteriori precisazioni e recapiti circa i servizi sociali contattati, le scuole che verranno frequentate dai figli, l'appartamento locato e l'offerta di collaborazione professionale ricevuta. Per il Presidente della Camera di protezione, a sfavore dell'attribuzione della custodia dei figli al padre depone poi il fatto che, dalla separazione dei genitori, egli non ha più contribuito finanziariamente al mantenimento dei tre figli e, in via abbondanziale, il fatto che egli ha rifiutato di riconsegnare i figli alla madre dopo le vacanze estive del 2018 senza alcuna giustificazione valida e contravvenendo alle decisioni dell'autorità di protezione.
Il Presidente della Camera di protezione ha quindi confermato la decisione di prima istanza.
3.3. Il ricorrente ribadisce che nel caso concreto si debba partire da un modello di presa a carico dei figli di tipo paritario tra i genitori e sostiene che il bene dei minori sarebbe meglio salvaguardato permettendo loro di rimanere ad Y._ con il padre. Dopo la permanenza di un anno in una casa protetta, il trasferimento in Austria rappresenterebbe infatti un ulteriore sradicamento per i figli, considerato che la loro lingua materna è in realtà l'italiano e che ad Y._ sono scolarizzati, hanno amici e frequentano diverse attività. I minori avrebbero del resto espresso il desiderio di restare nel Cantone Ticino e gli psicologi che avrebbero ascoltato i figli si sarebbero dichiarati sfavorevoli al loro trasferimento all'estero. Il progetto di vita della madre in Austria sarebbe in realtà vago e non documentato, e comunque motivato dalla sola intenzione di allontanare i figli dal padre. Quanto alla propria capacità genitoriale, sostiene che l'ordine di riconsegnare i figli alla madre dopo le vacanze estive 2018 sarebbe stato subordinato alla condizione che ella dimostrasse di avere una dimora abitativa nel Cantone Ticino e, data la mancata realizzazione di tale condizione, l'inosservanza di tale ordine sarebbe quindi stata orientata all'esclusivo interesse dei figli.
3.4. Le argomentazioni ricorsuali, ancora una volta, si fondano su circostanze che non risultano dall'accertamento fattuale operato dal Giudice cantonale (come il fatto che i figli avrebbero espresso il desiderio di rimanere ad Y._, che il trasferimento in Austria sarebbe motivato dalla sola intenzione della madre di separare i figli dall'altro genitore e che l'ordine di riconsegna dei minori sarebbe stato condizionato) o che lo contraddicono (ad esempio in relazione alla lingua materna dei figli o alla concretezza del progetto di vita in Austria dell'opponente). Il ricorrente accenna ad una violazione dell'<ref-law> "per arbitrario apprezzamento dei fatti e valutazione delle prove" (v. <ref-law>; supra consid. 1.2), ma tale censura non è minimamente concretizzata. Egli inoltre non pretende che la condizione dell'<ref-law> per poter allegare fatti nuovi sarebbe realizzata (v. supra consid. 1.2).
Ora, alla luce dei fatti invece constatati nella sentenza impugnata, l'apprezzamento del Presidente della Camera di protezione secondo cui il bene dei minori risulta meglio tutelato permettendo loro di seguire la madre nel suo paese di origine appare corretto. È vero che essi dovranno così affrontare un ulteriore cambiamento del luogo di dimora, questo unico fattore tuttavia non basta per giustificare l'attribuzione della loro custodia al ricorrente. La decisione contestata risulta pertanto conforme al diritto federale.
4.
Da quanto precede discende che il ricorso va respinto nella misura della sua ammissibilità.
La domanda di assistenza giudiziaria del ricorrente va respinta, il rimedio non avendo fin dall'inizio probabilità di successo (<ref-law>). Le spese giudiziarie sono pertanto poste a suo carico (<ref-law>). Non sono dovute ripetibili, dato che l'opponente ha dovuto pronunciarsi soltanto sulla domanda di conferimento dell'effetto sospensivo, risultando soccombente (<ref-law>). La contestazione di tale domanda era sprovvista di reali possibilità di esito favorevole (data l'assenza di urgenza; v. <ref-ruling> consid. 4; <ref-ruling> consid. 4.2.2), per cui anche la richiesta dell'opponente di essere posta al beneficio dell'assistenza giudiziaria va respinta (nella misura in cui non sia divenuta priva d'oggetto; <ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1.
Nella misura in cui è ammissibile, il ricorso è respinto.
2.
La domanda di assistenza giudiziaria del ricorrente è respinta.
3.
Nella misura in cui non è priva d'oggetto, la domanda di assistenza giudiziaria dell'opponente è respinta.
4.
Le spese giudiziarie di fr. 2'000.-- sono poste a carico del ricorrente.
5.
Comunicazione ai partecipanti al procedimento e al Presidente della Camera di protezione del Tribunale d'appello del Cantone Ticino.