Faits :
A.
Par jugement du 20 juillet 2015, le Tribunal de police de Genève a acquitté B._ du chef d'infraction à l'art. 19 al. 1 de la loi fédérale sur les stupéfiants et les substances psychotropes du 3 octobre 1951 (LStup; RS 812.121), l'a reconnu coupable de séjour illégal au sens de l'art. 115 al. 1 let. b de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20) et l'a condamné à une peine pécuniaire de 70 jours-amende, d'un montant de 10 fr. l'unité, sous déduction de la détention subie avant jugement.
B.
Statuant sur recours du ministère public portant sur l'infraction à la LStup, la Cour de justice genevoise, Chambre pénale d'appel et de révision, l'a rejeté par arrêt du 8 février 2016. Elle a en outre réformé le jugement de première instance d'office (art. 404 al. 2 CPP), et a libéré B._ des fins de la poursuite, en particulier s'agissant de l'infraction de séjour illégal.
L'arrêt repose en substance sur les faits suivants.
B._, ressortissant guinéen, a séjourné en Suisse, du 15 décembre 2013 au 17 octobre 2014, puis du 1 er décembre 2014 au 12 mars 2015, alors qu'il ne disposait pas des autorisations requises et était démuni de documents d'identité ainsi que de moyens de subsistance. B._ est enregistré en Suisse depuis le 30 juillet 2010 et a été débouté de sa requête d'asile. A teneur d'un courriel du 8 avril 2015 du Service de la population vaudois, B._ faisait l'objet d'une décision de renvoi en force, mais il n'était pas possible d'organiser son renvoi car le Secrétariat d'État aux migrations (ci-après: SEM) n'avait pas obtenu de laissez-passer et le canton de Vaud, après avoir annoncé la disparition de l'intéressé, avait cessé son soutien à l'obtention de documents. Il s'est vu remettre un bon de sortie valable du 15 octobre au 14 décembre 2013. B._ a reconnu l'irrégularité de son séjour du 15 décembre 2013 au 17 octobre 2014 et du 1 er décembre 2014 au 12 mars 2015.
C.
Le Ministère public genevois forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt du 8 février 2016 et conclut à ce que B._ est reconnu coupable de séjour illégal au sens de l'art. 115 al. 1 let. b LEtr et condamné à une peine pécuniaire de 70 jours-amende, d'un montant de 10 fr. l'unité, sous déduction de la détention avant jugement. Le recours porte sur la seule infraction à la LEtr, à l'exclusion de l'infraction à la LStup.
Invité à se déterminer sur le mémoire de recours, B._ a conclu, avec suite de frais et dépens, à son rejet et à la confirmation de l'arrêt cantonal. Il sollicite le bénéfice de l'assistance judiciaire. La cour cantonale a renoncé à se prononcer sur le mémoire de recours et s'est référée à son arrêt.

Considérant en droit :
1.
Selon le recourant, en retenant de façon toute générale qu'en l'absence de mesures de contrainte, aucune sanction pour séjour illégal au sens de l'art. 115 al. 1 let. b LEtr ne peut être prononcée, on permet à toute personne sans titre de séjour de persister à séjourner impunément en Suisse pendant de longues périodes sans encourir de sanction. Cette interprétation contreviendrait à la volonté du législateur et à la jurisprudence fédérale constante.
1.1. L'art. 115 al. 1 let. b LEtr punit d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire quiconque séjourne illégalement en Suisse, notamment après l'expiration de la durée du séjour non soumis à autorisation ou du séjour autorisé.
En cas d'exécution immédiate du renvoi ou de l'expulsion, le juge peut renoncer à poursuivre l'étranger sorti ou entré illégalement, à le renvoyer devant le tribunal ou à lui infliger une peine (art. 115 al. 4 LEtr). Il est question de modifier cette dernière disposition afin de l'adapter à la jurisprudence européenne rendue en la matière (cf. infra consid. 1.8).
1.2. Par accord du 26 octobre 2004, entré en vigueur le 1 er mars 2008 (Accord entre la Confédération suisse, l'Union européenne et la Communauté européenne sur l'association de la Confédération suisse à la mise en oeuvre, à l'application et au développement de l'acquis de Schengen; RS 0.362.31, ci-après : AAS), la Suisse s'est engagée à mettre en oeuvre et appliquer l'acquis de Schengen.
Le 16 décembre 2008, le Parlement européen et le Conseil de l'Union européenne ont adopté la Directive relative aux normes et procédures communes applicables dans les É tats membres au retour des ressortissants de pays tiers en séjour irrégulier (Directive 2008/115/CE; ci-après: Directive sur le retour). Celle-ci vise une harmonisation minimale des procédures d'éloignement et de rapatriement pour les ressortissants de pays non-membres de Schengen (pays tiers) en séjour irrégulier, afin que les personnes concernées soient rapatriées de façon humaine et dans le respect de leurs droits fondamentaux.
Par arrêté fédéral du 18 juin 2010, la Suisse a repris le contenu de cette Directive en tant que développement de l'acquis de Schengen (Arrêté fédéral portant approbation et mise en oeuvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la Directive CE sur le retour; RO 2010 5925; cf. Message du 18 novembre 2009 sur l'approbation et la mise en oeuvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la directive CE sur le retour et sur une modification de la LEtr, in: FF 2009 p. 8043; échange de notes, in: FF 2009 p. 8085; arrêté fédéral portant approbation et mise en oeuvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la directive CE sur le retour, in FF 2009 p. 8077). La mise en oeuvre de cette directive a requis une adaptation de la LEtr et de la loi fédérale du 26 juin 1998 sur l'asile (LAsi; RS 142.31); l'art. 115 al. 1 LEtr n'a, à ce jour, pas été modifié.
Comme le rappelle le Conseil fédéral dans son message, il est dans l'intérêt de toutes les parties que les règles instaurées par Schengen soient interprétées et appliquées de manière identique de part et d'autre (Message du 1 er octobre 2004 relatif à l'approbation des accords bilatéraux entre la Suisse et l'Union européenne, y compris les actes législatifs à la transposition des accords [" accords bilatéraux II"], FF 2004 5593 ss ch. 2.6.7.6). L'AAS a ainsi instauré un comité mixte qui a notamment pour mission d'observer l'application de cet accord par les différentes parties. S'il constate une différence substantielle dans l'interprétation et l'application de l'acquis de Schengen entre les autorités et juridictions suisses et la Cour de justice de l'Union européenne (ci-après: CJUE), il peut engager la procédure de règlement des différends prévue aux art. 9 al. 2 et 10 AAS qui peut aboutir, en cas d'échec, à la cessation de l'application de l'AAS.
1.3. La Directive sur le retour prévoit à son art. 6 que les États membres prennent une décision de retour à l'encontre de tout ressortissant d'un pays tiers en séjour irrégulier sur leur territoire. Selon l'art. 7 par. 1, la décision de retour fixe un délai approprié allant de sept à trente jours pour le départ volontaire, sans préjudice des exceptions visées aux par. 2 et 4. Certaines obligations visant à éviter le risque de fuite, comme les obligations de se présenter régulièrement aux autorités, de déposer une garantie financière adéquate, de remettre des documents ou de demeurer en un lieu déterminé, peuvent être imposées pendant le délai de départ volontaire (art. 7 par. 3). S'il existe un risque de fuite, ou si une demande de séjour régulier a été rejetée comme étant manifestement non fondée ou frauduleuse, ou si la personne concernée constitue un danger pour l'ordre public, la sécurité publique ou la sécurité nationale, les États membres peuvent s'abstenir d'accorder un délai de départ volontaire ou peuvent accorder un délai inférieur à sept jours (art. 7 par. 4).
Sous le titre marginal " éloignement ", l'art. 8 de la Directive sur le retour prévoit que les É tats membres prennent toutes les mesures nécessaires pour exécuter la décision de retour si aucun délai n'a été accordé pour un départ volontaire (cf. art. 7 par. 4), ou si l'obligation de retour n'a pas été respectée dans le délai accordé pour le départ volontaire conformément à l'art. 7. Les art. 15 ss de la Directive sur le retour règlent les conditions de rétention à des fins d'éloignement. En principe, à moins que d'autres mesures suffisantes, mais moins coercitives, puissent être appliquées efficacement dans un cas particulier, les É tats membres peuvent uniquement placer en rétention le ressortissant d'un pays tiers qui fait l'objet de procédures de retour afin de préparer le retour et/ou de procéder à l'éloignement (art. 15).
1.4. La CJUE a examiné la compatibilité de législations nationales prévoyant diverses sanctions (notamment l'amende ou l'emprisonnement) en cas de séjour illégal avec la Directive sur le retour. La jurisprudence européenne ayant évolué au fil des années et des questions posées par les autorités judiciaires nationales, il y a lieu de mettre en évidence les principes dégagés en matière de punissabilité du séjour illégal.
1.4.1. A teneur de l'arrêt El Dridi, la Directive sur le retour (notamment ses art. 15 et 16) s'oppose à une réglementation qui prévoit une peine d'emprisonnement à un ressortissant d'un pays tiers en séjour irrégulier pour le seul motif que celui-ci demeure, en violation d'un ordre de quitter le territoire de cet État dans un délai déterminé, sur ledit territoire sans motif justifié. Les États doivent poursuivre leurs efforts en vue de l'exécution de la décision de retour qui continue de produire ses effets. Ce n'est que dans l'hypothèse où l'exécution de la décision de retour sous forme d'éloignement risque d'être compromise par le comportement de l'intéressé que les États peuvent procéder à la privation de liberté de ce dernier au moyen d'une rétention. Celle-ci doit être aussi brève que possible et maintenue qu'aussi longtemps que le dispositif d'éloignement est en cours et exécuté avec toute la diligence requise (arrêt CJUE C-61/11 du 28 avril 2011 par. 39 s., 58 et 62). La Directive sur le retour établit l'ordre de déroulement des étapes de la procédure de retour correspondant à une gradation des mesures à prendre en vue de l'exécution de la décision de retour, gradation allant de la mesure qui laisse le plus de liberté à l'intéressé (octroi d'un délai pour un départ volontaire) à des mesures qui restreignent le plus celle-ci (rétention dans un centre spécialisé) (arrêt CJUE C-61/11 PPU du 28 avril 2001 CJUE par. 41). Dans cet arrêt, la CJUE n'a pas expressément répondu à la première question préjudicielle de l'État membre relative à la possibilité générale de sanctionner pénalement la violation d'une étape intermédiaire de la procédure administrative de retour (non-respect du seul ordre d'éloignement) avant que celle-ci ne soit achevée (arrêt CJUE C-61/11 du 28 avril 2011 par. 25).
1.4.2. Dans l'arrêt Achughbabian, la CJUE rappelle que la Directive sur le retour ne s'oppose pas à ce que le droit d'un État membre qualifie le séjour irrégulier de délit et prévoie des sanctions pénales pour dissuader et réprimer la commission d'une telle infraction aux règles nationales en matière de séjour (arrêt CJUE C-329/11 du 6 décembre 2011 par. 28). En revanche, elle retient que cette Directive s'oppose à une réglementation permettant l'emprisonnement d'un ressortissant d'un pays tiers qui, tout en séjournant irrégulièrement sur le territoire dudit État et n'étant pas disposé à quitter ce territoire volontairement, n'a pas été soumis aux mesures coercitives visées à l'art. 8 et n'a pas, en cas de placement en rétention en vue de la préparation et de la réalisation de son éloignement, vu expirer la durée maximale de cette rétention. Enfin, selon la CJUE, la Directive sur le retour ne s'oppose pas à l'emprisonnement d'un ressortissant d'un pays tiers auquel la procédure de retour établie par la Directive a été appliquée et qui séjourne irrégulièrement sur ledit territoire sans motif justifié de non-retour (arrêt CJUE C-329/11 du 6 décembre 2011 par. 50). A teneur de cet arrêt, le prononcé d'une décision de retour (fixant ou non un délai pour le départ volontaire) fait naître l'obligation imposée par l'art. 8 de la Directive sur le retour à l'État concerné, de prendre toutes les mesures nécessaires pour procéder à l'éloignement (cf. art. 3 par. 5), à savoir le transfert physique de l'intéressé hors de l'État (arrêt CJUE C-329/11 du 6 décembre 2011 par. 35). Or, l'infliction et l'exécution d'une peine d'emprisonnement au cours de la procédure de retour ne contribuent pas à la réalisation de l'éloignement que cette procédure poursuit. Une telle peine ne constitue donc pas une " mesure " ou une " mesure coercitive " au sens de l'art. 8 de la Directive (arrêt CJUE C-329/11 du 6 décembre 2011 par. 37).
1.4.3. Dans l'affaire Sagor, la CJUE rappelle que la Directive sur le retour ne s'oppose pas à ce que le droit d'un État membre qualifie le séjour irrégulier de délit et prévoie des sanctions pénales pour dissuader et réprimer la commission d'une telle infraction (arrêt CJUE C-430/11 du 6 décembre 2012 par. 31; cf. également arrêt Achughbabian précité par. 28). La CJUE considère que le prononcé d'une peine pécuniaire (pouvant être remplacée par une peine d'expulsion) n'empêche en aucune manière qu'une décision de retour soit prise et mise en oeuvre dans le plein respect des conditions énoncées aux art. 6 à 8 de la Directive et ne porte pas non plus atteinte aux normes communes en matière de privation de liberté énoncées aux art. 15 et 16 (arrêt CJUE C-430/11 du 6 décembre 2012 par. 36, 47, 50). En l'occurrence, le retour peut être réalisé indépendamment de la poursuite pénale et sans que celle-ci doive avoir abouti (arrêt CJUE C-430/11 du 6 décembre 2012 par. 35). En revanche, l'infliction et l'exécution d'une assignation à résidence au cours de la procédure de retour ne contribuent pas à la réalisation de l'éloignement. Une telle peine ne constitue donc pas une mesure ou une mesure coercitive au sens de l'art. 8 de la Directive. Un risque d'atteinte à la procédure de retour existe notamment si la réglementation applicable ne prévoit pas que l'exécution d'une peine d'assignation à résidence doit prendre fin dès qu'il est possible de réaliser l'éloignement (arrêt CJUE C-430/11 du 6 décembre 2012 par. 43 ss, 47, 50).
1.4.4. L'arrêt Zaizoune met en évidence l'obligation imposée par l'art. 8 de la Directive sur le retour de procéder à l'éloignement du ressortissant étranger en séjour irrégulier, dans les meilleurs délais (arrêt CJUE C-38/14 du 23 avril 2015 par. 34). Ainsi, une réglementation qui prévoit, en cas de séjour irrégulier d'imposer, selon les circonstances, soit une amende, soit l'éloignement en tant que mesures exclusives l'une de l'autre (l'amende étant incompatible avec l'éloignement du territoire national) est contraire aux principes issus de la Directive sur le retour (arrêt CJUE C-38/14 du 23 avril 2015 par. 41 s.).
1.4.5. Dans l'arrêt Celaj, la CJUE considère que la Directive sur le retour ne s'oppose pas, en principe, à une réglementation qui prévoit une peine d'emprisonnement à un ressortissant d'un pays tiers en situation de séjour irrégulier qui, après être retourné dans son pays d'origine dans le cadre d'une procédure de retour antérieure, entre de nouveau irrégulièrement sur le territoire dudit État en violation d'une interdiction d'entrée (arrêt CJUE C-290/2014 du 1 er octobre 2015 par. 33).
1.4.6. L'arrêt Affum traite de la pénalisation d'une personne en transit et conclut que la Directive sur le retour doit être interprétée en ce sens qu'elle s'oppose à une réglementation permettant, du seul fait de l'entrée irrégulière par une frontière intérieure conduisant au séjour irrégulier, l'emprisonnement d'un ressortissant d'un pays tiers, pour lequel la procédure de retour établie par cette directive n'a pas encore été menée à son terme (arrêt CJUE C-47/15 du 7 juin 2016 par. 93 s.).
1.5. En définitive, il ressort en substance de la jurisprudence européenne que la Directive sur le retour ne s'oppose pas à la pénalisation du séjour illégal. Celle-ci ne doit toutefois pas mettre en péril le renvoi effectif de l'intéressé. Or, le prononcé ou l'exécution d'une peine privative de liberté peut empêcher ou entraver le bon déroulement de la procédure de renvoi. Une telle sanction n'est compatible avec la Directive sur le retour qu'à condition que l'intéressé a été soumis aux mesures coercitives visées à l'art. 8 de la Directive sur le retour. La peine pécuniaire n'est quant à elle pas susceptible d'entraver la procédure de retour établie par la Directive, pour autant que l'État concerné respecte son obligation de prendre une décision de retour à l'encontre du ressortissant d'un pays tiers en séjour irrégulier et que la sanction n'exclut pas l'éloignement de l'intéressé.
1.6. Sur le plan interne, le Tribunal fédéral a fixé des principes en matière de punissabilité du séjour illégal selon l'art. 115 al. 1 let. b LEtr.
1.6.1. De jurisprudence constante, la punissabilité du séjour irrégulier suppose que l'étranger ne se trouve pas dans l'impossibilité objective - par exemple en raison d'un refus du pays d'origine d'admettre le retour de leurs ressortissants ou de délivrer des papiers d'identité - de quitter la Suisse et de rentrer légalement dans son pays d'origine. En effet, le principe de la faute suppose la liberté de pouvoir agir autrement (arrêt 6B_320/2013 du 29 août 2013 consid. 2.1 et les arrêts cités; cf. également arrêts 6B_139/2014 du 5 août 2014 consid. 2; 6B_482/2010 du 7 octobre 2010 consid. 3.2.2 et 3.2.3).
Dans un arrêt du 7 octobre 2010, rendu avant les arrêts topiques de la CJUE, le Tribunal fédéral a considéré que le ressortissant étranger faisant l'objet d'une décision de renvoi avec ordre de quitter la Suisse immédiatement, qui disparaissait après l'entrée en force de la décision et ne collaborait d'aucune manière à l'établissement de documents de voyage, se rendait coupable d'infraction à l'art. 115 al. 1 let. b LEtr. Il ne pouvait faire valoir l'impossibilité objective de quitter la Suisse. Sa condamnation à une peine pécuniaire de 70 jours-amende avec sursis ne prêtait pas flanc à la critique (arrêt 6B_482/2010 du 7 octobre 2010).
1.6.2. Depuis les arrêts principaux El Dridiet Achughbabian, le Tribunal fédéral a rendu plusieurs arrêts sur la compatibilité de l'application de l'art. 115 al. 1 let. b LEtr avec la Directive sur le retour. Compte tenu de l'évolution de la jurisprudence européenne et des adaptations que celle-ci implique sur le plan national, il y a lieu d'exposer succinctement les arrêts rendus par le Tribunal fédéral depuis 2011 (arrêts El Dridiet Achughbabian), respectivement, fin 2012 (arrêt Sagor).
En substance, selon le Tribunal fédéral, la Directive sur le retour n'exclut pas l'application des dispositions pénales nationales lorsque les autorités administratives ont entrepris toutes les mesures raisonnables pour l'exécution de la décision de retour mais que la procédure de retour a échoué en raison du comportement de l'intéressé (arrêts 6B_139/2014 du 5 août 2014 consid. 2; 6B_173/2013 du 19 août 2013 consid. 1.4; 6B_188/2012 du 17 avril 2012 consid. 5 et les arrêts cités). Sous cet angle, ces arrêts ne s'opposent pas à la jurisprudence européenne.
Dans quatre affaires, les recours formés contre des condamnations du chef de séjour illégal à des peines privatives de liberté allant de 2 à 6 mois ont été rejetés dans la mesure où aucune démarche administrative supplémentaire en vue du renvoi des recourants n'était exigible, faute de collaboration de ces derniers (arrêts 6B_188/2012 du 17 avril 2012 consid. 5 et 6B_525/2014 du 9 octobre 2014 consid. 1.2) ou faute de se trouver dans une hypothèse visée par les arrêts européens (arrêts 6B_196/2012 du 24 janvier 2013 consid. 2.1.3 et 2.2 et 6B_320/2013 du 29 août 2013 consid. 3, ce dernier arrêt étant critiqué en doctrine sous l'angle de l'art. 2 par. 2 let. b de la Directive sur le retour, cf. CATHERINE HAGUENAU-MOIZARD, La pénalisation du séjour irrégulier en droit européen, en droit français et en droit suisse, in Schengen et Dublin en pratique [Stephan Breitenmoser et al. (éd.)], 2015, p. 183 et ALEXANDRA BÜCHLER, die Konsequenzen des rechtswidrigen Aufenhalts von Drittstaatsangehörigen in der Schweiz, in Annuaire du droit de la migration 2015/2016, p. 107). Dans deux arrêts du 11 mars 2013 (arrêts 6B_617/2012 et 6B_618/2012 consid. 1.5), le Tribunal fédéral a admis les recours formés par le ministère public contre les classements prononcés en faveur de prévenus du chef de séjour illégal (peines privatives de liberté de 3 mois prononcées en première instance), considérant que toutes les mesures administratives raisonnables en vue du renvoi avaient été entreprises (notamment demandes d'établissement de papiers de voyage) et retenant que les prévenus refusaient de rentrer volontairement dans leur pays. Par ailleurs, tenant compte des circonstances des cas d'espèce, le Tribunal fédéral a considéré que les peines privatives de liberté de 3 mois prononcées en première instance n'étaient pas de nature à empêcher ou entraver l'expulsion des prévenus (arrêts 6B_617/2012 et 6B_618/2012 du 11 mars 2013 consid. 1.5, ces arrêts ont été commentés en doctrine, cf. MINH SON NGUYEN, Jurisprudence et analyses du 1 er janvier au 30 juin 2013, in Dang/Petry [éd.] Actualité du droit des étrangers, 2013, vol. 1, p. 57, selon lequel le manque de collaboration des prévenus n'est pas pertinent dès lors qu'il appartient, dans ce cas, à l'État d'entreprendre des mesures coercitives au sens de l'art. 8 de la Directive sur le retour; CATHERINE HAGUENAU-MOIZARD, op. cit., p. 182 et ALEXANDRA BÜCHLER, op. cit., p. 106, considèrent quant à elles que ces arrêts respectent la Directive sur le retour, respectivement la jurisprudence européenne).
Dans un arrêt du 19 avril 2013 (arrêt 6B_713/2012 consid. 1.5), le Tribunal fédéral a considéré qu'à la lumière de la jurisprudence européenne, la seule affirmation du ressortissant étranger selon laquelle il ne souhaitait pas quitter la Suisse n'était pas suffisante pour fonder sa culpabilité de séjour illégal, en l'absence de mise en place de mesures administratives. Il ressortait toutefois des pièces du dossier que le prévenu avait été renvoyé de force en 2001, qu'il faisait l'objet d'une décision de renvoi prononcée en 2009, que la police cantonale compétente était chargée de son expulsion et qu'il avait par la suite disparu. Le Tribunal fédéral a ainsi retenu que toutes les démarches administratives raisonnables pour l'exécution du renvoi avaient été entreprises et a rejeté le recours formé contre la condamnation du recourant à une peine pécuniaire de 60 jours-amende pour séjour illégal (arrêt 6B_713/2012 du 19 avril 2013 consid. 1.5). Par arrêt du 5 août 2014, le Tribunal fédéral a considéré que le prononcé d'une peine pécuniaire de 40 jours-amende avec sursis n'empêchait pas ni n'entravait la procédure de retour de sorte que cette condamnation du chef de séjour illégal ne prêtait pas flanc à la critique (arrêt 6B_139/2014 du 5 août 2014 consid. 3). Il ressortait de l'état de fait de cette affaire que les autorités administratives n'avaient entrepris aucune mesure de contrainte dès lors que le recourant semblait organiser personnellement son retour (arrêt 6B_139/2014 du 5 août 2014 consid. 3).
Dans des arrêts plus récents, le Tribunal fédéral a admis les recours formés contre la condamnation du chef de séjour illégal, faute pour les autorités administratives compétentes d'avoir entrepris les mesures de contrainte nécessaires en vue du renvoi (arrêts 6B_1172/2014 du 23 novembre 2015 et 6B_106/2016 du 7 décembre 2016). Dans l'arrêt 6B_1172/2014, le Tribunal fédéral a en outre considéré que la peine pécuniaire (60 jours-amende) était propre à entraver et à retarder le retour de la recourante et contrevenait à la Directive sur le retour. La recourante a dès lors été acquittée (arrêt critiqué par ALEXANDRA BÜCHLER, op. cit., p. 108, selon laquelle, cet arrêt semble, d'une part, reconnaître une priorité générale de la procédure de renvoi sur la procédure pénale, indépendamment du type de peine prononcé et, d'autre part, omettre que l'arrêt Sagor retient précisément qu'une peine pécuniaire n'entrave pas la procédure de renvoi). Dans son arrêt 6B_106/2016 du 7 décembre 2016, le Tribunal fédéral a jugé que la peine privative de liberté de 45 jours infligée au recourant contrevenait à la Directive sur le retour, la procédure de renvoi n'ayant pas été menée jusqu'à son terme sans succès. L'arrêt cantonal a été annulé et renvoyé à la cour cantonale pour nouvelle décision.
1.7. En doctrine, certains auteurs déduisent des arrêts El Dridiet Achughbabian que la procédure pénale doit être précédée par la procédure administrative de retour avec toutes ses étapes. La condamnation pénale n'est admise qu'en cas d'impossibilité de mise en oeuvre de mesures coercitives en vue du renvoi (THOMAS HUGI YAR, Das Urteil El Dridi, die EU-Rückführungsrichtlinie und der Schengen-Besitzstand, in jusletter du 11 juillet 2011, n° 11, 16; ANDREAS ZÜND, in Spescha et al. [éd.], Kommentar Migrationsrecht, 4e éd. 2015, n° 9 ad art. 80, n° 12 ad art. 115 LEtr; SARAH PROGIN-THEUERKAUF, Zur Auslegung der Begriffe " Massnahmen " und " Zwangsmassnahmen " in Art. 8 Abs. 1 und 4 der Eu-Rückführungsrichtlinie, in Revue Suisse pour la pratique et le droit d'asile, Asyl 2/12, p. 37). Le principe de l'opportunité posé à l'art. 115 al. 4 LEtr constituerait ainsi un véritable obstacle à la poursuite pénale (ANDREAS ZÜND, ibidem). Ces avis de doctrine, hormis celui de ZÜND, précèdent la jurisprudence européenne rendue fin 2012.
Prenant en compte la jurisprudence européenne postérieure, en particulier l'arrêt Sagor, d'autres auteurs estiment que la procédure pénale, voire la sanction pénale (sous forme de peine pécuniaire), sont possibles tant qu'elles ne privent pas la Directive sur le retour de son effet utile, ce même pendant la procédure administrative de renvoi (ALEXANDRA BÜCHLER, op. cit., p. 94 s., 102 s. et 104; CATHERINE HAGUENAU-MOIZARD, op. cit., p. 175 et 182; MINH SON NGUYEN, op. cit., p. 54 et 56). En référence à l'arrêt Sagor, ZÜND indique qu'une simple peine pécuniaire n'entrave pas la procédure de retour, de sorte que celle-ci est admissible (ANDREAS ZÜND, op. cit., n° 12 ad art. 115 LEtr).
1.8.
1.8.1. En juin 2016, le Conseil fédéral a lancé la procédure de consultation relative à la révision de la LEtr, notamment afin d'adapter cette dernière à la Directive sur le retour, à la suite de l'évaluation Schengen de la Suisse en 2014. Le projet de loi propose une modification de l'art. 115 al. 4 LEtr en ce sens que, lorsqu'une procédure de renvoi est prévue ou pendante, l'autorité compétente pourra renoncer à poursuivre pénalement, à renvoyer devant le tribunal ou à infliger une peine à un étranger illégalement entré en Suisse ou sorti de Suisse ou qui y séjourne illégalement. D'après le rapport explicatif, la modification proposée permet la primauté de l'exécution d'un renvoi sur une peine privative de liberté, dans le sens de la jurisprudence fédérale et européenne, non seulement si le renvoi est possible dans l'immédiat, mais aussi tant qu'une procédure de renvoi est pendante ou lorsqu'une telle procédure doit être ouverte en application de la Directive sur le retour (cf. Rapport explicatif, Adaptations de la loi sur les étrangers (LEtr) " Normes procédurales et systèmes d'information ", Commentaire de l'art. 115 al. 4 P-LEtr, p. 37; cf. THOMAS HUGI YAR, op. cit., n° 16; ALEXANDRA BÜCHLER, op. cit., p. 109 s., qui estiment nécessaire de clarifier la subsidiarité de la procédure pénale à la procédure d'éloignement par le biais de l'art. 115 al. 4 LEtr).
1.8.2. Compte tenu de la jurisprudence européenne et fédérale et conformément à l'opinion de la doctrine la plus récente, force est de constater que, en l'état, l'art. 115 al. 4 LEtr - lequel ne vise pas expressément le séjour illégal - ne saurait être interprété comme obstacle général à la poursuite pénale en cas de mise en oeuvre d'une procédure administrative de renvoi. Ce d'autant que le législateur s'est saisi de la question sous forme potestative (Kann-Vorschrift) dans le projet de modification de la LEtr.
1.9. Au vu de ce qui précède, il sied de retenir que la Directive sur le retour ne s'oppose pas à ce que le droit pénal suisse réprime le séjour illégal lorsqu'une procédure de retour est mise en oeuvre. En ce sens, elle ne s'oppose pas à ce que le séjour illégal soit érigé en infraction. Sur le plan de la sanction, une application de l'art. 115 al. 1 let. b LEtr conforme à la Directive sur le retour et à la jurisprudence européenne impose qu'il soit renoncé à prononcer et à exécuter une peine privative de liberté lorsque l'intéressé en séjour illégal fait l'objet d'une décision de renvoi et que les mesures nécessaires pour procéder à l'éloignement n'ont pas encore été mises en oeuvre. C'est la solution adoptée par l'arrêt du Tribunal fédéral le plus récent qu'il convient de suivre (arrêt 6B_106/2016 du 7 décembre 2016). En revanche, le prononcé d'une peine pécuniaire n'est pas incompatible avec la Directive sur le retour, pour autant qu'elle n'entrave pas la procédure de retour. Un telle sanction ne nécessite pas, à teneur de la jurisprudence européenne rendue à ce jour, que toutes les mesures nécessaires au renvoi aient préalablement été mises en oeuvre. En cela, il y a lieu de s'écarter de la solution retenue dans l'arrêt 6B_1172/2014 du 23 novembre 2015, critiqué par la doctrine (cf. ALEXANDRA BÜCHLER, op. cit., p. 108).
2.
En l'espèce, la cour cantonale a acquitté l'intimé en considérant que la procédure administrative de renvoi n'avait pas été menée à son terme, le cas échéant par le biais de mesures de contrainte prévues par la LEtr.
Or, s'il est vrai que l'absence de mesure administrative nécessaire à l'exécution du retour empêche le prononcé d'une peine privative de liberté, rien ne s'oppose à ce l'intimé soit reconnu coupable de séjour illégal, pour autant que les conditions de l'infraction soient réalisées.
D'une part, il est établi et non contesté que l'intimé a séjourné illégalement en Suisse du 15 décembre 2013 au 17 octobre 2014 et du 1 er décembre 2014 au 12 mars 2015, d'autre part, il n'était pas dans une situation d'impossibilité objective de retour (cf. jugement de première instance du 20 juillet 2015 consid. 2.1.2, notamment sur les accords conclus entre la Guinée et la Suisse), ce qu'il admet d'ailleurs (cf. mémoire de réponse, p. 3). L'intimé ne saurait invoquer l'état de nécessité (art. 17 CP) en se référant à un courrier du 19 avril 2015 par lequel il aurait sollicité auprès du SEM une admission provisoire pour inexigibilité du renvoi en raison du virus d'Ebola, dans la mesure où ce courrier est postérieur aux périodes pénales incriminées. En tout état, il n'expose d'aucune manière en quoi la situation en Guinée constituerait un danger imminent impossible à détourner autrement qu'en séjournant illégalement sur le territoire suisse. L'intimé ne saurait rien déduire en sa faveur d'un acquittement prononcé par le Tribunal de police genevois le 31 août 2016, du chef de séjour illégal. Aussi, au vu des développements qui précèdent (cf. supra consid. 1), il y a lieu de reconnaître l'intimé coupable de séjour illégal au sens de l'art. 115 al. 1 let. b LEtr. En acquittant l'intimé de ce chef d'infraction, la cour cantonale a violé le droit fédéral.
3.
Reste à déterminer si la peine pécuniaire ferme de 70 jours-amende (sous déduction de 2 jours-amende) à 10 fr. l'unité, prononcée en première instance et requise par le recourant, est compatible avec la Directive sur le retour.
3.1. Il ressort de l'arrêt Sagor que le prononcé d'une peine pécuniaire n'empêche en aucune manière qu'une décision de retour soit prise et mise en oeuvre pour autant que l'éloignement puisse être réalisé indépendamment de la poursuite pénale et sans que celle-ci doive avoir abouti. L'arrêt Zaizoune n'exclut le prononcé d'une amende que si cette sanction est incompatible, en vertu du droit national, avec l'éloignement du territoire national (cf. supra consid. 1.4.3, 1.4.4 et 1.5). Les avis de doctrine les plus récents admettent, sur la base de la jurisprudence européenne, qu'une peine pécuniaire n'entrave pas la procédure de retour de sorte qu'elle est admissible (cf. supra consid. 1.7).
3.2. En l'espèce, il ressort de la décision de première instance et des documents figurant au dossier (notamment les extraits de la base de données fédérales SYMIC) que l'intimé a déposé une demande d'asile le 29 juillet 2010, a été attribué au canton de Vaud et a fait l'objet, le 12 mars 2012, d'une décision de non-entrée en matière et de renvoi, décision entrée en force le 11 avril 2012. Le renvoi de l'intimé n'a pas été exécuté, les autorités vaudoises ayant signalé la disparition de l'intéressé et le Secrétariat d'État aux migrations n'ayant pas obtenu de laissez-passer (cf. jugement de première instance, consid. B.b.a p. 3).
Ainsi, si la procédure de renvoi n'a pas été menée jusqu'à son terme par les autorités administratives, ce n'est pas le prononcé d'une peine pécuniaire qui l'a entravée. Cette sanction ne s'oppose dès lors pas à la Directive sur le retour et à la jurisprudence européenne rendue en la matière (cf. supra consid. 1).
3.3. Au vu de ce qui précède, le recours du ministère public doit être admis, l'arrêt entrepris annulé et la cause renvoyée à la cour cantonale afin qu'elle reconnaisse l'intimé coupable de séjour illégal (art. 115 al. 1 let. b LEtr) et qu'elle fixe une peine conformément aux considérants qui précèdent (cf. en outre <ref-ruling> consid. 3.2 p. 9; arrêt 6B_1226/2013 du 31 mars 2014 consid. 1.1 sur le délit continu).
4.
Le ministère public, qui obtient gain de cause, ne saurait se voir allouer de dépens (art. 68 al. 3 LTF). La requête d'assistance judiciaire de l'intimé doit être admise au vu de sa situation financière et une indemnité appropriée doit être accordée à son conseil d'office, à charge de la caisse du Tribunal fédéral (art. 64 al. 2 LTF). L'intimé est toutefois rendu attentif au fait qu'il devra rembourser cette dernière, s'il peut ultérieurement le faire (art. 64 al. 4 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision.
2.
La demande d'assistance judiciaire de l'intimé est admise pour la procédure devant le Tribunal fédéral.
3.
Il n'est pas perçu de frais judiciaires.
4.
Me Dina Bazarbachi est désignée comme avocat d'office de l'intimé et une indemnité de 1'000 fr., supportée par la caisse du Tribunal fédéral, lui est allouée à titre d'honoraires.
5.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 15 mai 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke