Faits :
A.
B._ et A._ se sont mariés en 1994. Ils sont les parents de C._ et D._, nés respectivement en 2006 et en 2010. Les enfants sont binationaux, leur mère étant de nationalité canadienne et leur père de nationalité suisse.
Par décision du 20 mars 2014, le Tribunal civil de l'arrondissement de la Sarine a prononcé le divorce des époux B._ et A._. Il a attribué l'autorité parentale conjointe aux parents et la garde des enfants à la mère, le père disposant d'un droit de visite.
B._ s'est remariée avec E._. De cette union est né un enfant prénommé F._.
B.
B.a. Par acte du 18 mai 2015, B._ a requis de la Justice de paix de l'arrondissement de la Sarine (ci-après: Justice de paix) l'autorisation de modifier le lieu de résidence de ses enfants au Québec (Canada), région dont elle est originaire et où vit sa famille.
Se déterminant sur cette demande, A._ a conclu à ce qu'une expertise pédopsychiatrique de C._ et D._ ainsi qu'une évaluation sociale aux domiciles maternel et paternel soient ordonnées. Au fond, il a conclu principalement au rejet de la demande et, subsidiairement, à ce que B._ soit autorisée à modifier son propre lieu de résidence, la garde des enfants étant confiée au père et un droit de visite étant accordé à la mère, frais d'exercice de celui-ci à la charge de cette dernière. Plus subsidiairement, il a conclu à ce que la mère soit autorisée à modifier son lieu de résidence et celui des enfants au Québec, un droit de visite étant accordé au père, frais d'exercice du droit de visite à la charge de la demanderesse. Il a par la suite modifié ses conclusions en ce sens qu'il a supprimé sa conclusion plus subsidiaire. Il a en revanche confirmé sa demande d'expertise pédopsychiatrique.
A la demande de la Justice de paix, le Service de l'enfance et de la jeunesse (ci-après: SEJ) a rendu un rapport d'enquête sociale en date du 16 décembre 2015. Le SEJ a proposé que la garde des enfants reste confiée à la mère, celle-ci étant autorisée à s'installer au Canada avec eux au terme d'une année scolaire, que le père bénéficie d'un droit de visite aussi large que possible, à savoir de quatre semaines durant les vacances d'été et, en alternance, de deux semaines à Noël et de deux semaines à Pâques pour autant que ce rythme soit supportable pour les enfants et que les frais inhérents au droit de visite soient répartis équitablement entre les parents, et que le père et les enfants puissent communiquer aussi souvent que possible par exemple par " skype ", à raison de deux soirs par semaine.
Le SEJ a complété son rapport d'enquête en date du 24 mars 2016 après s'être entretenu avec la psychologue scolaire et les pédiatres des enfants. Il a confirmé les propositions faites dans son précédent rapport.
Le 5 avril 2016, les parties ont comparu devant la Justice de paix, de même que E._ en qualité de témoin. Le 15 avril 2016, la Juge de paix s'est en outre entretenue avec les enfants.
Par décision du 27 avril 2016, la Justice de paix a rejeté la requête du père tendant à ordonner une expertise psychiatrique sur ses enfants ainsi que celle visant à l'audition de son frère, de sa soeur et du père de B._. Elle a également autorisé cette dernière à déplacer le lieu de résidence des enfants au Québec (Canada) à partir du 1er août 2016, étant entendu que ceux-ci commenceraient leur nouvelle scolarité au Canada. L'autorité parentale conjointe a été maintenue et la garde est restée confiée à la mère, le père disposant d'un droit de visite qui s'exercerait à raison de quatre semaines durant les vacances d'été et, en alternance, deux semaines à Noël et deux semaines à Pâques. De plus, en dehors des vacances, le père communiquerait aussi souvent que possible avec ses enfants mais au minimum une fois par semaine, soit par " skype ", soit par téléphone, à 18h15 (heure au Canada, soit 12h15 en Suisse [recte: 18h15 en Suisse, soit 12h15 au Canada]). Les frais de déplacement des enfants pour l'exercice du droit de visite ont été mis à la charge du père, lequel n'aurait plus à verser de pensions alimentaires.
B.b. Par mémoire du 27 mai 2016, le père a interjeté recours contre cette décision concluant à son annulation, à ce qu'une expertise pédopsychiatrique sur ses enfants soit ordonnée et au rejet de la requête en modification du lieu de résidence de ceux-ci; subsidiairement, il a conclu à ce que la mère soit autorisée à modifier son lieu de résidence, à ce que la garde des enfants soit confiée à leur père et à ce qu'un droit de visite soit accordé à leur mère, qui s'acquitterait des frais d'exercice du droit de visite; très subsidiairement, il a conclu au renvoi de la cause à l'autorité intimée pour nouvelle décision dans le sens des considérants, frais à la charge de la mère.
Par arrêt du 8 juillet 2016, la Cour de protection de l'adulte et de l'enfant du Tribunal cantonal de l'Etat de Fribourg a rejeté le recours et a confirmé la décision querellée.
C.
Par acte posté le 10 août 2016, A._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt du 8 juillet 2016. Il conclut à son annulation et à sa réforme en ce sens qu'une expertise pédopsychiatrique des enfants des parties est ordonnée et que la requête de la mère en modification du lieu de résidence de ceux-ci est rejetée. Subsidiairement, il sollicite le renvoi de la cause à l'autorité cantonale pour nouvelle décision dans le sens des considérants. Le recourant requiert en outre l'effet suspensif et le bénéfice de l'assistance judiciaire pour la procédure fédérale.
Invitée à se déterminer sur la requête d'effet suspensif, l'intimée a, par acte du 29 août 2016, conclu à son rejet dans la mesure de sa recevabilité, alléguant notamment que le déplacement de la famille au Canada était désormais effectif. La cour cantonale a, quant à elle, renoncé à se déterminer sur la requête d'effet suspensif.
Des observations sur le fond n'ont pas été requises.
D.
Par ordonnance présidentielle du 1er septembre 2016, la requête d'effet suspensif a été déclarée sans objet compte tenu du fait que l'intimée se trouve désormais au Canada avec les deux enfants des parties.

Considérant en droit :
1.
Le recours a été déposé en temps utile (<ref-law>) contre une décision finale (<ref-law>) rendue en matière civile (<ref-law>) par une autorité supérieure statuant sur recours en dernière instance cantonale (art. 75 al. 1 et 2 LTF), dans une cause de nature non pécuniaire. Le recourant a en outre pris part à la procédure devant l'autorité précédente (<ref-law>) et a un intérêt digne de protection à l'annulation ou à la modification de la décision attaquée (<ref-law>). Le recours en matière civile est donc recevable au regard des dispositions précitées.
2.
2.1. Il ressort des écritures sur effet suspensif et des pièces produites à leur appui que l'intimée a, après le 1er août 2016, quitté la Suisse pour le Canada avec ses deux enfants et qu'ils sont désormais installés dans ce pays. Il y a lieu de tenir compte de ce fait nouveau en tant qu'il est susceptible d'influer sur la compétence des juridictions suisses.
2.2. Le Canada, où se trouvent actuellement les enfants, n'est pas partie à la Convention de La Haye du 5 octobre 1961 concernant la compétence des autorités et la loi applicable en matière de protection des mineurs (CLaH61; RS 0.211.231.01) ni ne l'a ratifiée. Il n'est pas non plus signataire de la Convention de La Haye du 19 octobre 1996 concernant la compétence, la loi applicable, la reconnaissance, l'exécution et la coopération en matière de responsabilité parentale et de mesures de protection des enfants (CLaH96; RS 0.211.231.011). Ce nonobstant, cette dernière convention est applicable en l'espèce en raison du renvoi de l'<ref-law> (arrêts 5A_274/2016 du 26 août 2016 consid. 2.1; 5A_809/2012 du 8 janvier 2013 consid. 2.3.1 et les références citées). Dès lors que le principe de la perpetuatio foriest applicable lorsque l'enfant se trouve dans un Etat non contractant à la CLaH96 - ou dans un Etat qui ne l'a pas ratifiée -, il suffit que les enfants aient eu leur résidence habituelle en Suisse au moment du dépôt de la requête tendant à autoriser leur déménagement au Canada, à savoir le 18 mai 2015, peu importe qu'ils se soient ou non constitués une nouvelle résidence au Canada depuis cette date (cf. arrêts 5A_274/2016 précité consid. 2.4; 5A_809/2012 précité consid. 2.4). Or, il n'est pas contesté que tel est le cas en l'espèce. La compétence des juridictions suisses pour statuer dans la présente cause est par conséquent donnée.
3.
3.1. Le recours en matière civile peut être interjeté pour violation du droit fédéral (<ref-law>), y compris le droit constitutionnel (<ref-ruling> consid. 2.1; <ref-ruling> consid. 2.4). Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est pas lié par l'argumentation des parties (<ref-ruling> consid. 1.3) et apprécie librement la portée juridique des faits. Il s'en tient cependant en principe aux questions juridiques que la partie recourante soulève dans la motivation du recours (<ref-law>); il n'est pas tenu de traiter, à l'instar d'une juridiction de première instance, toutes les questions juridiques pouvant se poser lorsqu'elles ne sont plus discutées devant lui (<ref-ruling> consid. 2; <ref-ruling> consid. 1.3; <ref-ruling> consid. 2.2.1; <ref-ruling> consid. 1.4). Le recourant doit discuter les motifs de la décision entreprise et indiquer précisément en quoi il estime que l'autorité précédente a méconnu le droit (<ref-law>; <ref-ruling> consid. 2). Le grief doit être développé dans le recours même, un renvoi à d'autres écritures ou à des pièces n'étant pas admissible (<ref-ruling> consid. 2.8.1; <ref-ruling> consid. 3.2). Il doit exister un lien entre la motivation du recours et la décision attaquée. Le recourant doit se déterminer par rapport aux considérants de l'arrêt entrepris et expliquer en quoi ceux-ci sont à son avis contraires au droit; il ne peut se contenter de reprendre presque mot pour mot l'argumentation formée devant l'autorité cantonale (<ref-ruling> consid. 2; <ref-ruling> consid. 2.1 et 2.3; FLORENCE AUBRY GIRARDIN, Commentaire de la LTF, 2ème éd., n° 30 ad <ref-law> et les arrêts cités).
Par exception à la règle selon laquelle il applique le droit d'office, le Tribunal fédéral ne connaît de la violation de droits fondamentaux que si de tels griefs ont été invoqués et motivés par le recourant conformément au principe d'allégation (<ref-law>), c'est-à-dire s'ils ont été expressément soulevés et exposés de façon claire et détaillée (<ref-ruling> consid. 2.2; <ref-ruling> consid. 3.3; <ref-ruling> consid. 1.2, 397 consid. 1.4 in fine). Les critiques de nature appellatoire sont irrecevables (<ref-ruling> consid. 2.3; <ref-ruling> consid. 10.1 et les arrêts cités).
3.2. Le Tribunal fédéral conduit son raisonnement sur la base des faits établis par la juridiction précédente (<ref-law>); il ne peut s'en écarter que si ces faits ont été constatés de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). La partie recourante qui soutient que les faits ont été constatés d'une manière manifestement inexacte (<ref-law>), c'est-à-dire arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 5.4, 336 consid. 2.4.1; <ref-ruling> consid. 2.3 précité; <ref-ruling> consid. 1.2.2), doit satisfaire au principe d'allégation susmentionné (cf. supra consid. 3.1 in fine), sous peine d'irrecevabilité. Elle ne peut, en particulier, se contenter d'opposer sa thèse à celle de la juridiction cantonale, mais doit s'efforcer de démontrer, par une argumentation précise, que la décision attaquée repose sur une appréciation des preuves manifestement insoutenable.
4.
Le recourant soulève tout d'abord une violation de son droit d'être entendu (art. 29 al. 2 Cst.). Il reproche à l'autorité cantonale d'avoir considéré que l'instruction menée par la Justice de paix était suffisante et que, dès lors, il ne se justifiait pas d'ordonner l'expertise pédopsychiatrique qu'il avait sollicitée.
Hormis la critique consistant à dire que la cour cantonale n'a pas tenu compte des propos diffamatoires de E._ relatés dans l'acte de recours cantonal, et l'allégation selon laquelle C._ lui avait confié à lui seul que la psychologue le traitait de nul, la motivation présentée par le recourant est strictement identique à celle contenue aux pages 7 et 8 de son acte de recours cantonal. Or, le procédé consistant à reprendre mot pour mot l'argumentation soumise aux juges précédents ne répond en rien aux exigences de motivation rappelées ci-dessus (cf. supra consid. 3.1).
C'est le lieu de relever que les développements contenus dans le chapitre intitulé " Préambule " du présent recours n'y changent rien, en tant qu'ils ne constituent qu'une simple introduction et qu'ils ont en définitive une teneur similaire aux griefs articulés dans le corps du mémoire. Même s'il l'agrémente d'un préambule, le recourant ne saurait dès lors se croire autorisé à recopier son mémoire de recours cantonal, sous prétexte que " l'arrêt de la Cour de protection de l'enfant et de l'adulte (...) n'apporte rien de plus, en terme[s] de raisonnement juridique, que la décision de la Justice de paix ". Ce faisant, le recourant perd complètement de vue que le recours en matière civile obéit à des règles dans l'exposé des moyens, lesquelles sont au demeurant strictes s'agissant de griefs d'ordre constitutionnel (cf. supra consid. 3.1 in fine).
S'agissant des deux seuls éléments ajoutés dans le présent recours, on ne saisit pas quelle serait leur pertinence par rapport au grief de violation du droit d'être entendu soulevé. La cour cantonale a procédé à une appréciation anticipée de la preuve proposée par le recourant, qui l'a conduite à admettre que celle-ci ne pourrait plus l'amener à modifier sa conviction acquise sur la base des preuves déjà recueillies (cf. <ref-ruling> consid. 4.3.2). Ce nonobstant, le recourant ne démontre pas en quoi cette appréciation anticipée des preuves serait insoutenable. Or, l'on ne peut s'en prendre à une telle appréciation qu'en soulevant le grief d'arbitraire (art. 9 Cst.), motivé selon les exigences strictes de l'<ref-law> (parmi plusieurs: arrêt 4A_11/2015 du 25 juin 2015 consid. 2.1; cf. supra consid. 3.2).
Il s'ensuit que le grief est irrecevable.
5.
Invoquant l'<ref-law>, le recourant fait ensuite grief à la cour cantonale d'avoir procédé à un établissement inexact des faits. Il critique ainsi la constatation selon laquelle les angoisses de C._ étaient simplement dues à l'incertitude d'un départ et qu'aucune investigation supplémentaire n'était nécessaire. Or, les angoisses de son fils étaient déjà présentes en 2012 et il existait un risque qu'elles soient liées aux déménagements et à l'instabilité de l'intimée. Le recourant s'en prend également au constat selon lequel l'entente entre les enfants et E._ serait bonne et que celui-ci aurait à coeur de leur offrir un environnement stable et sécurisant. C'était oublier que l'actuel mari de l'intimée avait giflé C._, que, selon les enfants, il criait beaucoup, qu'il se faisait appeler " papi " par D._, qu'il l'avait frappé devant les enfants, et qu'il avait dit à C._ que son père était " un merdeux, qui fait que de la merde ".
Là encore, force est de constater que cette critique ne respecte pas les exigences de motivation susrappelées, le recourant oubliant manifestement que le Tribunal fédéral n'est pas une cour d'appel (cf. supra consid. 3.1 et 3.2). Elle s'épuise, quoi qu'il en soit, en un " copié-collé " des pages 8 et 9 du mémoire de recours cantonal, ce qui en scelle d'emblée le sort pour les motifs évoqués ci-dessus (cf. supra consid. 4).
6.
Sous couvert d'une violation des <ref-law> et 13 al. 1 Cst., le recourant soutient, dans un chapitre intitulé " Conclusion ", que l'intérêt " primordial " des enfants s'oppose à un départ au Québec.
Il n'y a pas davantage lieu d'entrer en matière sur ce moyen. Il s'agit en effet, une fois encore, d'une reprise textuelle du mémoire de recours cantonal (p. 10-13). Les exigences de motivation (art. 42LTF; cf. supra consid. 3.1) ne sont, ce faisant, nullement respectées.
7.
Enfin, le recourant se plaint, pour la première fois devant le Tribunal fédéral, de la réglementation du droit de visite telle qu'arrêtée par la Justice de paix et confirmée par la cour cantonale. La qualifiant d'impraticable, il soutient que le calendrier scolaire québécois ne permettrait pas l'exercice d'un droit de visite de deux semaines à Pâques. La semaine manquante devrait ainsi être au moins compensée par une semaine supplémentaire pendant les vacances d'été.
Il résulte de l'arrêt entrepris que le recourant n'a pas contesté ce point devant l'autorité cantonale. Il ressort aussi des faits arrêtés par les juges précédents qu'il avait retiré sa conclusion " plus subsidiaire " relative à l'exercice de son droit de visite en cas de déplacement des enfants au Canada. Présenté à ce stade, le moyen, manifestement contraire aux règles de la bonne foi, apparaît tardif. Force est également de constater qu'il se fonde sur des éléments ne résultant pas de l'état de fait de l'arrêt attaqué, qui lie le Tribunal fédéral (<ref-law>; cf. supra consid. 3.2). Il ne saurait dès lors être entré en matière sur ce grief. Quoi qu'il en soit, on ne voit pas que l'autorité cantonale, qui dispose sur cette question d'un large pouvoir d'appréciation en vertu de l'<ref-law> (cf., parmi plusieurs, arrêt 5A_422/2015 du 10 février 2016 consid. 4.2, non publié aux <ref-ruling>), se serait écartée des éléments du dossier et qu'elle aurait effectué une pondération de ceux-ci contraire aux principes jurisprudentiels pour déterminer l'étendue et les modalités du droit de visite.
8.
En conclusion, le recours est irrecevable. Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>). Sa requête d'assistance judiciaire est rejetée, le recours étant d'emblée dépourvu de chances de succès (<ref-law>). L'intimée, qui n'a pas été invitée à se déterminer sur le fond mais qui a, en définitive, eu gain de cause sur l'effet suspensif, a droit à une indemnité de dépens pour ses déterminations y relatives, mise à la charge du recourant (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est irrecevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Une indemnité de 500 fr., à payer à titre de dépens à l'intimée, est mise à la charge du recourant.
5.
Le présent arrêt est communiqué aux parties et à la Cour de protection de l'enfant et de l'adulte du Tribunal cantonal de l'Etat de Fribourg.
Lausanne, le 26 septembre 2016
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : von Werdt
La Greffière : Mairot