Faits:
A.
A.a. A._, né en 1984, et B._, née en 1973, tous deux de nationalité française, sont les parents non mariés de C._, née en 2013.
A.b.
A.b.a. Actuellement, A._ est domicilié à D._ (France). Il travaille à Genève et est au bénéfice d'une autorisation frontalière (G) délivrée le 9 janvier 2012. B._ est domiciliée avec C._ à E._, en Suisse. Elle travaille à Genève et est au bénéfice d'une autorisation de séjour B.
A.b.b. Auparavant, les parties, qui s'étaient rencontrées en août 2010 à Y._ (USA), avaient emménagé ensemble dans cette ville en juillet 2011 puis s'étaient séparées à la fin du mois d'août 2011. B._ avait alors été hébergée par des proches à E._. Pour sa part, A._ s'était établi plus tard à F._ (France), puis, les parties s'étant réconciliées, dans l'appartement de B._ à E._. Durant la grossesse de celle-ci, le couple avait ensuite habité à D._ (France) dans un appartement dont le bail prévoyait une durée du 14 décembre 2012 au 13 décembre 2015.
A.b.c. Le 19 janvier 2013, A._ a reconnu l'enfant à naître devant l'officier d'état civil de D._ (France).
L'enfant est née à Genève. Selon son acte de naissance suisse, sa mère est domiciliée à E._ et son père à D._. En revanche, selon son extrait de naissance français, ses parents sont tous deux domiciliés à D._.
L'enfant et sa mère ont quitté la maternité le 14 juin 2013 et se sont rendues dans l'appartement de D._.
A.b.d. Le 19 juin 2013, B._ a quitté l'appartement de D._ avec l'enfant pour s'installer à E._, d'abord chez des proches puis dans un appartement loué depuis le 1 er septembre 2013.
B._ n'a pas sollicité l'accord de A._ avant de partir avec l'enfant en Suisse.
B.
B.a. Le 11 juillet 2013, B._ a formé une requête devant le Tribunal de première instance de Genève en fixation de la contribution d'entretien de l'enfant et en remboursement de certains frais.
Le 12 juillet 2013, elle a formé une requête en fixation des relations personnelles devant le Tribunal de protection de l'adulte et de l'enfant à Genève, aux fins de faire constater qu'elle est titulaire de l'autorité parentale sur C._ et de solliciter l'attribution du droit de garde sur l'enfant.
B.b. Le 29 juillet 2013, A._ a assigné B._ en la forme des référés devant le Juge aux Affaires Familiales du Tribunal de Grande Instance de Thonon-les-Bains (France) afin qu'il soit statué sur les modalités de l'exercice de l'autorité parentale (autorité parentale, droit de visite et contribution d'entretien).
Par jugement du 22 octobre 2013, le tribunal s'est déclaré compétent pour statuer sur le litige, en application du droit français. Il a rejeté l'exception de litispendance soulevée par B._, a ordonné une enquête sociale et a renvoyé la cause au 25 mars 2014. A titre provisoire dans l'attente du dépôt du rapport d'enquête sociale, le tribunal a statué sur la résidence de C._ (chez B._), le droit de visite du père (un jour par semaine jusqu'au 23 novembre 2013, puis élargi) et la contribution d'entretien due à l'enfant (400 euros).
L'autorité française a considéré que la résidence habituelle de l'enfant avant le 19 juin 2013 se situait en France et que C._ avait été déplacée illicitement en Suisse en violation du droit de garde du père, détenteur de l'autorité parentale en vertu du droit français. En raison de cette illicéité, l'enfant ne pouvait acquérir de nouvelle résidence habituelle hors de France, de sorte que la compétence française était maintenue et que le droit français s'appliquait à la cause. Dès lors, s'agissant de l'autorité parentale, elle a constaté que l'exercice de l'autorité parentale était commun de plein droit. Néanmoins, s'agissant de la résidence de l'enfant à titre provisoire, elle a considéré que la fixation d'une résidence alternée d'un enfant en bas âge n'était pas appropriée et qu'il ne pouvait pas être imposé à la mère de s'installer en France, relevant la proximité des résidences des parents de part et d'autre de la frontière franco-suisse.
C.
Le 15 août 2013, parallèlement à la procédure de droit de la famille engagée devant les autorités françaises, A._ a saisi la Cour de justice du canton de Genève d'une requête de retour au sens de la CLaH80 en vue du rapatriement immédiat en France de sa fille C._, concluant à ce qu'il soit ordonné à la mère de l'enfant de se conformer à ce chef de conclusions, sous menace de la peine de l'<ref-law>, avec suite de frais.
Par décision du 1 er novembre 2013, soit postérieurement à la décision française de mesures provisionnelles, l'autorité cantonale a rejeté cette requête.
D.
Par acte du 21 novembre 2013, A._ exerce un recours en matière civile contre cette décision. Il conclut, principalement, à sa réforme en ce sens que le retour immédiat en France de l'enfant soit ordonné sous la menace de la peine prévue à l'<ref-law> et, subsidiairement, à son annulation et au renvoi de la cause à l'autorité cantonale pour nouvelle décision au sens des considérants. En substance, il invoque la violation des art. 1 let. a, 3, 4, 13, 16 CLaH80, 17 CLaH96 et 9 Cst. dans l'application de la CLaH80.
Invitées à présenter leurs observations, l'intimée a conclu au rejet du recours, alors que l'autorité cantonale a persisté dans les motifs et le dispositif de sa décision.
Par courrier du 28 novembre 2013, l'intimée a requis d'être mise au bénéfice de l'assistance judiciaire.

Considérant en droit:
1.
Les décisions statuant sur le retour d'un enfant en application de la Convention de La Haye sur les aspects civils de l'enlèvement international d'enfants du 25 octobre 1980 (RS 0.211.230.02; CLaH80) ne sont pas des affaires civiles. Il s'agit d'entraide administrative entre les États contractants, donc d'une question relevant du droit public mais qui est en rapport direct avec le respect et la mise en oeuvre du droit civil étranger (art. 72 al. 2 let. b ch. 1 LTF; <ref-ruling> consid. 1.2). La Cour de justice du canton de Genève a statué en instance cantonale unique conformément à l'art. 7 al. 1 de la loi fédérale sur l'enlèvement international d'enfants et les Conventions de La Haye sur la protection des enfants et des adultes du 21 décembre 2007 (LF-EEA, RS 211.222.32); il y a ainsi exception légale au principe du double degré de juridictions cantonales (<ref-law>). Le délai légal de 10 jours (art. 100 al. 2 let. c LTF) est en outre respecté, de sorte que le recours en matière civile est en principe recevable.
2.
Le recours en matière civile peut être formé pour violation du droit fédéral et du droit international (art. 95 let. a et b LTF). Le Tribunal fédéral applique le droit d'office (<ref-law>) sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.2).
3.
3.1. L'autorité cantonale a jugé que la question du lieu de la résidence habituelle de l'enfant avant le déplacement pouvait demeurer indécise, étant donné que, de toute façon, une séparation du nourrisson d'avec sa mère placerait celui-ci dans une situation intolérable. Or, selon la cour, le retour de l'intimée avec l'enfant en France ne pouvait manifestement pas lui être imposé puisqu'elle obtiendra le droit de garde définitif sur sa fille et qu'il faut éviter un aller-retour provisoire.
3.2. Le recourant reproche à l'autorité cantonale d'avoir violé la CLaH80 en laissant ouverte la question de la résidence habituelle de l'enfant, alors que l'illicéité du déplacement dépend précisément du droit applicable en ce lieu, et d'avoir anticipé la décision française sur le droit de garde. Il précise que, selon le droit français, le déplacement est illicite, comme l'a d'ailleurs reconnu le juge français dans sa décision du 22 octobre 2013, alors qu'il ne le serait pas en vertu du droit suisse. Il reproche aussi à la cour d'avoir retenu qu'une exception au retour serait remplie, alors que tel n'est pas le cas, étant précisé que le retour n'impose pas à l'intimée de cohabiter avec lui.
4.
La question qui se pose est de savoir si le retour de l'enfant en France doit être ordonné en application de la CLaH80.
4.1. La France comme la Suisse ont ratifié aussi bien la CLaH80 que 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). En vertu de l'art. 50 CLaH96, la CLaH96 n'affecte cependant pas la CLaH80 dans les relations entre les États parties aux deux conventions, de sorte que le retour de l'enfant peut être demandé sur la base de la CLaH80 (arrêts 5A_637/2013 du 1 er octobre 2013 consid. 5.1.1; 5A_479/2012 du 13 juillet 2012 consid. 4.1, publié in PJA 2012 p. 1630, in SJ 2013 I p. 29 et in JdT 2013 II p. 152).
4.2.
4.2.1. L'ordonnance du retour de l'enfant suppose que le déplacement soit illicite. Selon l'art. 3 al. 1 let. a CLaH80, tel est le cas lorsque celui-ci a lieu en violation d'un droit de garde, attribué à une personne, seul ou conjointement, par le droit de l'Etat dans lequel l'enfant avait sa résidence habituelle immédiatement avant son déplacement. L'alinéa 2 de cette norme précise que le droit de garde peut notamment résulter d'une attribution de plein droit, d'une décision judiciaire ou administrative, ou d'un accord en vigueur selon le droit de cet Etat.
Pour déterminer le ou les parents titulaires du droit de garde, qui comprend en particulier celui de décider du lieu de résidence de l'enfant (art. 5 let. a CLaH80), il y a lieu de se référer à l'ordre juridique de l'État de la résidence habituelle de l'enfant immédiatement avant le déplacement (<ref-ruling> consid. 2.1.1; arrêt 5A_479/2012 du 13 juillet 2012 consid. 4.3, publié in SJ 2013 I p. 29, résumé in PJA 2012 p. 1630 et in JdT 2013 II p. 152). Ce moment est également déterminant pour juger de l'illicéité du déplacement (arrêt 5A_713/2007 du 28 février 2008 consid. 3, publié in PJA 2008 p. 1312 et in FamPra.ch 2008 p. 703).
La décision sur la garde de l'enfant revenant au juge du fond de l'Etat requérant, le juge de l'Etat requis n'a pas à effectuer un quelconque pronostic à cet égard; la procédure prévue par la CLaH80 a uniquement pour objet d'examiner les conditions auxquelles est subordonné le retour selon cette convention, de façon à permettre une décision future sur l'attribution de la garde par le juge du fond (<ref-ruling> consid. 2.4; arrêts 5A_637/2013 du 1 er octobre 2013 consid. 5.1.2; 5A_847/2012 du 17 décembre 2012 consid. 3.2.1).
4.2.2. En principe, lorsqu'un enfant a été déplacé ou retenu illicitement, l'autorité saisie ordonne son retour immédiat (art. 1 let. a, 3 et 12 al. 1 CLaH80), à moins qu'une exception prévue à l'art. 13 CLaH80 ne soit réalisée.
4.2.2.1. Une des exceptions au retour est l'existence d'un risque grave que le retour n'expose l'enfant à un danger physique ou psychique ou le place de toute autre manière dans une situation intolérable (art. 13 al. 1 let. b CLaH80; 5 LF-EEA).
Selon la jurisprudence, la séparation d'un nourrisson d'avec la mère constitue dans tous les cas une situation intolérable au sens précité. Néanmoins, le retour ne peut être refusé pour cette raison que si on ne peut imposer à la mère ravisseuse qu'elle raccompagne elle-même l'enfant. Il doit s'agir toutefois de situations exceptionnelles, dans lesquelles il ne peut être raisonnablement exigé de la mère qu'elle retourne dans le pays de dernière résidence de l'enfant aux fins d'y attendre qu'il soit jugé définitivement sur les droits parentaux (arrêt 5A_637/2013 du 1 er octobre 2013 consid. 5.1.2 et les références).
4.2.2.2. Lorsque l'Etat requérant rend, postérieurement au déplacement, une décision accordant la garde au parent ravisseur, il y a lieu d'admettre que le retour de l'enfant ne doit pas être ordonné, car une telle décision équivaut en quelque sorte à un acquiescement postérieur au sens de l'art. 13 al. 1 let. a CLaH80 ( PIRRUNG, in Staudinger, Kommentar zum BGB, 2009, n°D72 ad Vorbemerkungen zu Art. 19 EGBGB).
4.3. En l'espèce, l'autorité cantonale a violé les principes précités (cf. supra consid. 4.2), de sorte que les griefs du recourant à l'encontre de l'arrêt attaqué sont, sur ces points, fondés: premièrement, l'autorité cantonale ne pouvait pas se dispenser d'examiner la question de la résidence habituelle de l'enfant, étant donné que le droit de garde et, partant, l'illicéité du déplacement dépend du droit applicable en ce lieu; deuxièmement, elle n'était pas en droit d'anticiper la décision au fond sur la garde, étant donné que la décision ordonnant le retour n'a en principe pas d'autre but que de rétablir la situation telle qu'elle existait avant l'enlèvement; troisièmement, elle n'a pas examiné s'il existait une situation exceptionnelle empêchant impérativement l'intimée de raccompagner elle-même sa fille, qui, âgée de quelques mois seulement, ne pouvait être séparée d'elle.
Néanmoins, le recours doit être rejeté par substitution des motifs qui suivent. A supposer que, comme le soutient le recourant, le déplacement de l'enfant serait illicite en vertu du droit français applicable pour statuer sur la garde au vu de la résidence habituelle de l'enfant en France, il n'en demeure pas moins que, par décision du 22 octobre 2013, le juge français a provisoirement fixé la résidence de l'enfant auprès de l'intimée, en Suisse. Sur le vu de cette décision du juge du fond de l'Etat requérant, le retour de l'enfant n'avait pas à être ordonné. Les conclusions en réforme du recourant, tendant à l'admission de sa requête de retour, doivent donc être rejetées, sans qu'il y ait besoin d'examiner les autres griefs soulevés.
5.
En conclusion, le recours est rejeté. Les art. 26 CLaH80 et 14 LF-EEA prévoient la gratuité de la procédure; toutefois, conformément aux dispositions de l'art. 42 CLaH80 et par application de l'art. 26 al. 3 CLaH80, la France a déclaré qu'elle ne prendra en charge les frais visés à l'al. 2 de l'article 26 que dans la mesure où ces frais sont couverts par le système français d'aide judiciaire. La Suisse applique dans ce cas le principe de la réciprocité (art. 21 al. 1 let. b de la Convention de Vienne du 23 mai 1969 sur le droit des traités [RS 0.111]), de sorte que la procédure devant le Tribunal fédéral n'est pas gratuite (arrêts 5A_25/2010 du 2 février 2010 consid. 3; 5A_840/2011 du 13 janvier 2012 consid. 6). Le recourant, qui succombe, supportera ainsi les frais judiciaires (<ref-law>) arrêtés à 2'000 fr. Il versera en outre à l'intimée une indemnité de dépens à hauteur de 1'500 fr. (<ref-law>) pour l'instance fédérale (<ref-law>).
Il sera statué sur la requête d'assistance judiciaire de l'intimée, qui a encore été invitée à produire des pièces, par décision séparée.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Une indemnité de 1'500 fr., à payer à l'avocat de l'intimée à titre de dépens, est mise à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties, à la Cour de justice du canton de Genève, Autorité centrale cantonale, au Service de protection des mineurs et à l'Office fédéral de la justice, Autorité centrale en matière d'enlèvement international d'enfants.
Lausanne, le 19 décembre 2013
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président: von Werdt
La Greffière: Achtari