Faits :
A.
A._, ressortissant du Sénégal né le 15 février 1982, est entré légalement en Suisse le 11 avril 2008 en vue de son mariage avec une ressortissante suisse. A la suite de cette union célébrée le 6 juin 2008, A._ a été mis au bénéfice d'une autorisation de séjour. Les époux ont eu deux enfants, B._, né le 21 mars 2008, et C._, née le 15 mai 2010, qui sont de nationalité suisse. Le couple s'est séparé le 3 novembre 2012. Le Tribunal civil de l'arrondissement de l'Est vaudois a, le 7 février 2013, ratifié la convention de mesures protectrices de l'union conjugale établie par les époux. La garde des enfants a été attribuée à leur mère. A._ s'est vu accorder un libre droit de visite et a été astreint, dès qu'il aurait trouvé un emploi lui procurant un salaire mensuel net de 2'800 fr., au versement d'une contribution d'entretien de 800 fr. Il n'a jusqu'à présent pas versé de pensions alimentaires.
Depuis le mois de décembre 2015, A._ est employé deux jours par semaine, son revenu mensuel net s'élevant à 1'265 fr. 50. Jusqu'alors, il n'avait travaillé qu'épisodiquement. Depuis son arrivée en Suisse, A._ a été inscrit au chômage durant près de quatre mois et a bénéficié du revenu d'insertion de manière quasi ininterrompue, le montant total perçu à cet titre s'élevant à 218'755 fr. au 12 octobre 2015. Il est actuellement encore tributaire de cette aide. A._ ne fait pas l'objet de poursuites.
Sur le plan pénal, A._ a été condamné, par ordonnance pénale du Ministère public de la Confédération du 26 février 2015, à une peine pécuniaire de dix jours-amende pour falsification d'un timbre officiel.
B.
Par décision du 24 novembre 2014, le Service de la population du canton de Vaud a refusé de délivrer à A._ une autorisation d'établissement à titre anticipé. Il s'est en revanche déclaré disposé à renouveler son autorisation de séjour, sous réserve de l'approbation du Secrétariat d'Etat aux migrations (ci-après: SEM). Le 5 octobre 2015, celui-ci a refusé d'approuver la prolongation de l'autorisation de séjour en faveur de A._ et a prononcé son renvoi de Suisse. L'intéressé a contesté ce prononcé auprès du Tribunal administratif fédéral par acte du 6 novembre 2015. Par arrêt du 19 octobre 2016, le Tribunal administratif fédéral a rejeté le recours. Il a jugé en bref que A._ ne pouvait se prévaloir ni d'une intégration réussie, ni de raisons personnelles majeures.
C.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif, de réformer l'arrêt du Tribunal administratif fédéral du 19 octobre 2016 en ce sens que l'autorisation de séjour est prolongée; subsidiairement d'annuler l'arrêt entrepris et de renvoyer la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants.
Par ordonnance du 24 novembre 2016, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif.
Le Tribunal administratif fédéral a renoncé à prendre position. Le SEM a conclu au rejet du recours. Le recourant n'a pas formulé de nouvelles observations.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2.1 p. 397; <ref-ruling> consid. 2 p. 59).
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Le recourant fait valoir que les conditions de l'art. 50 al. 1 LEtr (RS 142.20) sont remplies. Le recours en matière de droit public est par conséquent recevable, étant précisé que le point de savoir si les conditions posées par la loi sont effectivement réunies relève de l'examen au fond (<ref-ruling> consid. 1.1 p. 332).
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (art. 90 LTF), rendue par le Tribunal administratif fédéral (art. 86 al. 1 let. a LTF) dans une cause de droit public (art. 82 let. a LTF). Le recours ayant de surcroît été déposé en temps utile (art. 100 al. 1 LTF) et dans les formes requises (art. 42 LTF), par le recourant qui est atteint par la décision entreprise et a un intérêt digne de protection à son annulation ou à sa modification, de sorte qu'il faut lui reconnaître la qualité pour recourir (art. 89 al. 1 LTF), il est partant recevable.
2.
Le recourant se plaint d'arbitraire dans l'établissement des faits et l'appréciation des preuves.
2.1. Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. En vertu de l'art. 97 LTF, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'art. 95 LTF, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-ruling> consid. 6 p. 358; <ref-ruling> consid. 4.2 p. 234; <ref-ruling> consid. 1.5 p. 129 s.).
2.2. Selon la jurisprudence, une décision est arbitraire lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une autre solution paraisse concevable, voire préférable; pour que cette décision soit annulée, encore faut-il qu'elle se révèle arbitraire non seulement dans ses motifs, mais aussi dans son résultat (<ref-ruling> consid. 2.1 p. 18 s.; <ref-ruling> consid. 7.1 p. 51; <ref-ruling> consid. 4.3 p. 319). Lorsque la partie recourante s'en prend à l'appréciation des preuves et à l'établissement des faits, la décision n'est arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée ou encore si, sur la base des éléments recueillis, il a procédé à des déductions insoutenables (<ref-ruling> consid. 6 p. 358; <ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 4.2 p. 234; <ref-ruling> consid. 4.2 p. 560). Il appartient à la partie recourante de démontrer l'arbitraire par une argumentation répondant aux exigences de l'art. 106 al. 2 LTF. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (ATF <ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 10.1 p. 445; <ref-ruling> consid. 5.1 p. 356).
2.3. En l'espèce, le recourant reproche à l'instance précédente de ne pas avoir retenu que la fréquence et la durée élevées de son droit de visite démontraient l'existence de liens économiques étroits entre lui et ses enfants. Cette question relève toutefois de l'appréciation juridique des faits, soit une question de droit qui sera traitée au consid. 4 infra, et non pas d'une question de fait, comme semble le croire le recourant.
2.4. Pour le surplus, dans la mesure où le recourant présente une argumentation partiellement appellatoire, en opposant sa propre version des faits à celle du Tribunal administratif fédéral ou en complétant librement l'état de fait, sans invoquer ni l'arbitraire, ni une constatation manifestement inexacte des faits, le Tribunal fédéral ne peut pas en tenir compte. Il statuera donc sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
3.
Le recourant se plaint d'une violation de l'art. 50 al. 1 let. a LEtr. Il fait valoir une intégration réussie.
3.1. Selon l'art. 50 al. 1 let. a LEtr, le droit du conjoint à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste si l'union conjugale a duré au moins trois ans et que l'intégration est réussie. Ces deux conditions sont cumulatives (<ref-ruling> consid. 3.5.3 p. 295; <ref-ruling> consid. 3.3.3 p. 119). En l'espèce, est seul litigieux le point de savoir si le recourant peut se prévaloir d'une intégration réussie.
3.2. Le principe de l'intégration doit permettre aux étrangers dont le séjour est légal et durable de participer à la vie économique, sociale et culturelle de la Suisse (art. 4 al. 2 LEtr). D'après l'art. 77 al. 4 de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), un étranger s'est bien intégré, au sens de l'art. 50 al. 1 let. a LEtr, notamment lorsqu'il respecte l'ordre juridique suisse et les valeurs de la Constitution fédérale (let. a) et qu'il manifeste sa volonté de participer à la vie économique et d'apprendre la langue nationale parlée au lieu de domicile (let. b). Selon l'art. 4 de l'ordonnance du 24 octobre 2007 sur l'intégration des étrangers (OIE; RS 142.205), la contribution des étrangers à l'intégration se manifeste notamment par le respect de l'ordre juridique et des valeurs de la Constitution fédérale (let. a), par l'apprentissage de la langue nationale parlée sur le lieu de domicile (let. b), par la connaissance du mode de vie suisse (let. c) et par la volonté de participer à la vie économique et d'acquérir une formation (let. d). L'adverbe "notamment", qui est employé tant à l'art. 77 al. 4 OASA qu'à l'art. 4 OIE, illustre le caractère non exhaustif des critères d'intégration qui sont énumérés par ces dispositions et met aussi en exergue le fait que la notion "d'intégration réussie" doit s'examiner à l'aune d'une appréciation globale des circonstances. Dans l'examen de ces critères d'intégration, les autorités compétentes disposent d'un large pouvoir d'appréciation que le Tribunal fédéral ne revoit qu'avec retenue (cf. art. 54 al. 2 et 96 al. 1 LEtr et art. 3 OIE; arrêts 2C_656/2016 du 9 février 2017 consid. 5.2; 2C_385/2016 du 4 octobre 2016 consid. 4.1; 2C_838/2015 du 3 mars 2016 consid. 4.1; 2C_861/2015 du 11 février 2016 consid. 5.3.1; 2C_151/2015 du 10 février 2016 consid. 3.2.1; 2C_352/2014 du 18 mars 2015 consid. 4.2 et les références).
3.3. Selon la jurisprudence, il n'y a pas d'intégration réussie lorsque l'étranger n'exerce pas d'activité lucrative qui lui permette de couvrir ses besoins et qu'il dépend des prestations sociales pendant une période relativement longue. A l'inverse, le fait pour une personne de ne pas avoir commis d'infractions pénales et de pourvoir à son revenu sans recourir à l'aide sociale ne permet pas à lui seul de retenir une intégration réussie (arrêts 2C_656/2016 du 9 février 2017 consid. 5.2; 2C_385/2016 du 4 octobre 2016 consid. 4.1; 2C_861/2015 du 11 février 2016 consid. 5.2; 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_14/2014 du 27 août 2014 consid. 4.6.1, non publié in <ref-ruling>). Des périodes d'inactivité de durée raisonnable n'impliquent pas forcément une absence d'intégration professionnelle. Il n'est pas indispensable que l'étranger fasse montre d'une carrière professionnelle requérant des qualifications spécifiques; l'intégration réussie au sens de l'art. 50 al. 1 let. a LEtr n'implique en effet pas nécessairement la réalisation d'une trajectoire professionnelle particulièrement brillante au travers d'une activité exercée sans discontinuité. L'essentiel en la matière est que l'étranger subvienne à ses besoins, n'émarge pas à l'aide sociale et ne s'endette pas de manière disproportionnée (arrêts 2C_656/2016 du 9 février 2017 consid. 5.2; 2C_385/2016 du 4 octobre 2016 consid. 4.1; 2C_838/2015 du 3 mars 2016 consid. 4.1; 2C_861/2015 du 11 février 2016 consid. 5.2; 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_385/2014 du 19 janvier 2015 consid. 4.1). L'intégration réussie d'un étranger qui est actif professionnellement en Suisse, dispose d'un emploi fixe, a toujours été financièrement indépendant, se comporte correctement et maîtrise la langue locale ne peut être niée qu'en la présence de circonstances particulièrement sérieuses (arrêts 2C_656/2016 du 9 février 2017 consid. 5.2; 2C_385/2016 du 4 octobre 2016 consid. 4.1; 2C_352/2014 du 18 mars 2015 consid. 4.3; 2C_930/2012 du 10 janvier 2013 consid. 3.1). L'absence de liens sociaux très étroits en Suisse n'exclut pas non plus d'emblée l'existence d'une intégration réussie, de même que l'absence de vie associative (arrêt 2C_656/2016 du 9 février 2017 consid. 5.2 et les références).
3.4. Sous l'angle de l'intégration professionnelle, il ressort de l'arrêt entrepris que le recourant a effectué un apprentissage de cinq mois, puis a, dans la période allant de son arrivée en Suisse à fin décembre 2012, occupé divers postes temporaires totalisant ensemble une durée de quelque deux ans. En 2015, il a travaillé pour une agence temporaire. Depuis le mois de décembre 2015, il est employé deux jours par semaine, son revenu mensuel net s'élevant à 1'265 fr. 50. Le recourant a été inscrit au chômage durant environ quatre mois durant son séjour en Suisse. Il a, de l'année 2008 au 12 octobre 2015, bénéficié du revenu d'insertion pour un montant totalisant 218'755 fr. Il dépend encore actuellement de cette aide dans une large mesure. Il découle de ces constatations - non contestées par le recourant -, que celui-ci a été inactif professionnellement plus de la moitié de son séjour en Suisse d'une part et qu'il n'a pas toujours été en mesure de s'assumer financièrement d'autre part. L'emploi qu'il exerce depuis décembre 2015, s'il permet de retenir une certaine volonté d'intégration professionnelle, ne lui permet par ailleurs pas de pourvoir à son entretien. La situation économique du recourant, illustrée par une dépendance à l'aide sociale persistante, a été et demeure ainsi précaire. Dans ces circonstances, force est de constater que le recourant n'est pas intégré professionnellement et ne peut se prévaloir d'une intégration économique réussie. A cela s'ajoute que le recourant n'a pas toujours eu un comportement entièrement respectueux de l'ordre juridique suisse, ayant fait l'objet d'une condamnation pénale pour avoir falsifié une vignette autoroutière, ce qui ne permet pas de conclure à une intégration sociale réussie.
Compte tenu de ce qui précède, l'appréciation globale du Tribunal administratif niant l'intégration réussie du recourant, en dépit des quelques éléments parlant en sa faveur (absence de poursuites, maîtrise d'une langue nationale, présence de membres de sa famille et d'un réseau social en Suisse, ainsi qu'exercice d'une activité professionnelle à temps partiel depuis décembre 2015), ne viole pas le droit fédéral des étrangers.
C'est en conséquence à bon droit que l'autorité précédente a jugé que le recourant ne remplit pas les conditions de l'art. 50 al. 1 let. a LEtr.
4.
Le recourant invoque une violation des art. 8 CEDH, 13 Cst. et 50 al. 1 let. b LEtr.
4.1. Selon l'art. 50 al. 1 let. b LEtr, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEtr subsiste lorsque la poursuite du séjour du recourant en Suisse s'impose pour des raisons personnelles majeures. De telles raisons peuvent en particulier découler d'une relation digne de protection avec un enfant qui a le droit de séjourner en Suisse (<ref-ruling> consid. 2.1 p. 318 s.). Dans ce cas, les conditions posées par l'art. 50 al. 1 let. b LEtr ne recoupent pas nécessairement celles de l'octroi d'un titre de séjour fondé sur l'art. 8 CEDH. Le droit au respect de la vie familiale garanti par les articles 8 CEDH et 13 Cst. doit néanmoins être pris en compte dans l'application de l'art. 50 al. 1 let. b LEtr, dont l'application ne saurait être plus restrictive que celle des articles 8 CEDH et 13 Cst. (arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.1; 2C_328/2016 du 14 novembre 2016 consid. 4.1; 2C_652/2013 du 17 décembre 2013 consid. 2.3 et les références, non publié in <ref-ruling> mais in RDAF 2015 I 401).
4.2. Le parent qui n'a pas l'autorité parentale ni la garde de l'enfant ne peut d'emblée entretenir une relation familiale avec celui-ci que de manière limitée, en exerçant le droit de visite dont il bénéficie. Or, il n'est en principe pas nécessaire que, dans l'optique de pouvoir exercer son droit de visite, le parent étranger soit habilité à résider durablement dans le même pays que son enfant. Sous l'angle du droit à une vie familiale (cf. art. 8 par. 1 CEDH et art. 13 al. 1 Cst.), il suffit en règle générale que le parent vivant à l'étranger exerce son droit de visite dans le cadre de séjours de courte durée, au besoin en aménageant ses modalités quant à la fréquence et à la durée (<ref-ruling> consid. 2.2 p. 319; arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.2; 2C_328/2016 du 14 novembre 2016 consid. 4.2). Le droit de visite d'un parent sur son enfant ne doit en effet pas nécessairement s'exercer à un rythme bimensuel et peut également être organisé de manière à être compatible avec des séjours dans des pays différents (arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.1; 2C_328/2016 du 14 novembre 2016 consid. 4.2 et 2C_1031/2011 du 22 mars 2012 consid. 4.2.3). Selon la jurisprudence constante du Tribunal fédéral, un droit plus étendu ne peut le cas échéant exister qu'en présence de liens familiaux particulièrement forts d'un point de vue affectif et économique, lorsque cette relation ne pourrait pratiquement pas être maintenue en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent, et que l'étranger a fait preuve en Suisse d'un comportement irréprochable (<ref-ruling> consid. 3.2 p. 147; <ref-ruling> consid. 2.2 p. 319 et les références; arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.1; 2C_328/2016 du 14 novembre 2016 consid. 4.2). Ces exigences doivent être appréciées ensemble et faire l'objet d'une pesée des intérêts globale (arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.2; 2C_165/2016 du 8 septembre 2016 consid. 5.2; 2C_723/2014 du 6 août 2015 consid. 2.3; 2C_728/2014 du 3 juin 2015 consid. 4.1 et 4.4). Dans le cadre de l'examen de la proportionnalité de la mesure (cf. art. 8 par. 2 CEDH, art. 96 LEtr et art. 13 cum art. 36 Cst.), il faut aussi tenir compte de l'intérêt fondamental de l'enfant (art. 3 de la Convention du 20 novembre 1989 relative aux droits de l'enfant [CDE; RS 0.107]) à pouvoir grandir en jouissant d'un contact étroit avec ses deux parents (arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.2; 2C_860/2016 du 2 décembre 2016 consid. 3.3.2; 2C_27/2016 du 17 novembre 2016 consid. 5.5.1; 2C_157/2016 du 13 octobre 2016 consid. 6.2; 2C_165/2016 du 8 septembre 2016 consid. 5.2; 2C_1125/2014 du 9 septembre 2015 consid. 4.2 et les références; cf. aussi arrêt de la CourEDH El Ghatet c. Suisse du 8 novembre 2016 [requête no 56971/10], par. 27 s. et 46 s.).
4.3. L'exigence du lien affectif particulièrement fort doit être considérée comme remplie lorsque les contacts personnels sont effectivement exercés dans le cadre d'un droit de visite usuel selon les standards d'aujourd'hui (en Suisse romande, il s'agit d'un droit de visite d'un week-end toutes les deux semaines et durant la moitié des vacances; arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.3; 2C_420/2015 du 1 er octobre 2015 consid. 2.3 et 2C_794/2014 du 23 janvier 2015 consid. 3.2), lorsque l'étranger détient déjà un droit de séjour en Suisse, de façon à prendre en compte l'art. 9 par. 3 de la CDE, sans toutefois déduire de cette convention une prétention directe à l'octroi d'une autorisation (<ref-ruling> consid. 3.2 p. 148; <ref-ruling> consid. 2.4 s. p. 320 s.).
4.4. Selon la jurisprudence, on ne saurait parler de comportement irréprochable lorsqu'il existe, à l'encontre de l'étranger des motifs d'éloignement, en particulier si l'on peut lui reprocher un comportement répréhensible sur le plan pénal ou en regard de la législation sur les étrangers (arrêts 2C_60/2016 du 25 mai 2016 consid. 4.2.3; 2C_762/2013 du 31 janvier 2014 consid. 5.1 in fine). Par ailleurs, en droit des étrangers, le respect de l'ordre et de la sécurité publics ne se recoupent pas nécessairement avec la violation de dispositions pénales, de sorte que l'appréciation émise par l'autorité de police des étrangers peut s'avérer plus rigoureuse que celle de l'autorité pénale (<ref-ruling> consid. 4.3 p. 150 s.).
4.5. En l'occurrence, il ressort des constatations de l'autorité précédente, qui lient le Tribunal de céans (cf. art. 105 al. 1 LTF), que le recourant ne jouit ni de l'autorité parentale exclusive ni du droit de garde sur ses enfants, de nationalité suisse. Il n'est pas contesté qu'il entretient un lien affectif particulièrement fort avec eux, les contacts personnels dépassant le cadre d'un droit de visite usuel selon les standards d'aujourd'hui. Il s'agit donc uniquement de déterminer si les liens familiaux sont particulièrement forts d'un point de vue économique. A cet égard, il résulte des faits de l'arrêt entrepris que le recourant n'a pas été en mesure de verser des contributions d'entretien en faveur de ses enfants. Il est cependant constaté que les pensions alimentaires auxquelles le recourant a été astreint n'ont vraisemblablement jamais été exigibles. Le juge civil a en effet ratifié une convention intervenue entre les époux, selon laquelle le recourant doit s'acquitter d'une pension alimentaire mensuelle de 800 fr. en faveur de ses enfants dès qu'il aura un emploi lui permettant de réaliser un salaire mensuel net de 2'800 fr. Or, l'activité professionnelle du recourant lui procure un revenu de 1'265 fr. 50 et il n'a auparavant travaillé qu'épisodiquement, dépendant presque constamment de l'aide sociale. Le recourant fait valoir à raison que l'entretien des parents ne se traduit pas seulement par le transfert d'argent, mais également par l'entretien quotidien, les soins et l'éducation (cf. art. 276 al. 2 CC; arrêt 2C_497/2014 du 26 octobre 2015 consid. 6.1). Il ne faut cependant pas perdre de vue que le recourant n'a, depuis son entrée en Suisse, pour ainsi dire jamais pratiqué d'activité professionnelle de nature à subvenir à ses besoins et à ceux de sa famille. La séparation de son couple et ses obligations d'entretien auraient dû le conduire à chercher activement un emploi lui permettant à la fois d'être autonome financièrement et de verser des pensions alimentaires, voire d'exercer un droit de visite étendu. Tel n'a pas été le cas. A cela s'ajoute que le recourant reconnaît que le non-versement des contributions d'entretien a pour but de lui permettre, de même qu'à la mère de ses enfants, d'entreprendre une formation. Dans ces conditions, il ne saurait être considéré que le recourant a la volonté de subvenir aux besoins de ses enfants, peu importe que la mère de ces derniers ait renoncé au versement des contributions d'entretien les concernant - ce qui n'est au demeurant pas établi. Quant à la possibilité que la formation suivie par le recourant lui permette d'obtenir des revenus stables et réguliers, elle n'entre pas en considération compte tenu de son caractère purement appellatoire. L'arrêt du Tribunal administratif fédéral doit donc être confirmé en tant qu'il constate l'absence de lien économique fort entre le recourant et ses enfants.
4.6. De plus, le recourant, qui a été condamné à une peine de dix jours-amende pour falsification d'un timbre officiel, ne saurait se targuer d'un comportement irréprochable, ce d'autant moins qu'il ne se trouve pas dans une des situations pour lesquelles la jurisprudence en la matière a été assouplie (<ref-ruling> consid. 4.1 p. 148 s.; arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.5; 2C_723/2014 du 6 août 2015 consid. 2.3; 2C_165/2014 du 18 juillet 2014 consid. 4.3; 2C_606/2013 du 4 avril 2014 consid. 5.3).
4.7. Ces circonstances, prises dans leur ensemble, à savoir l'absence de relations économiques particulièrement fortes entre le recourant et ses enfants, ainsi que le comportement en Suisse de l'intéressé, font apparaître que les précédents juges n'ont pas violé les articles 50 al. 1 let. b LEtr et 8 CEDH en considérant qu'il n'y avait pas de raison personnelle majeure imposant la poursuite du séjour du recourant dans ce pays.
5.
En dernier lieu, hormis les liens du recourant avec ses enfants, dont on a vu que, bien qu'il soit dans l'intérêt de ceux-ci de pouvoir grandir en jouissant d'un contact étroit avec les deux parents, ils ne justifient pas à eux seuls son séjour en Suisse, l'arrêt attaqué ne révèle aucun élément déterminant qui ferait apparaître le refus d'approuver la prolongation de l'autorisation de séjour de l'intéressé comme disproportionné (cf. art. 96 LEtr). Le grief du recourant, qui fait valoir de manière appellatoire que ses finances ne permettraient pas le maintien de son droit de visite en cas de retour au Sénégal, peut sans autre être écarté, étant précisé que le Tribunal administratif fédéral a tenu compte de la possibilité pour le recourant de conserver des liens avec ses enfants en dépit de l'éloignement (notamment par communication téléphonique et correspondance). Il en va de même de l'argument du recourant selon lequel il ne disposerait pas des moyens techniques d'entretenir de fréquents contacts épistolaires ou numériques avec ses enfants. L'autorité précédente a en outre pris en considération l'âge d'arrivée en Suisse du recourant, la durée et la qualité de son séjour en ce pays, le fait que son intégration professionnelle n'est pas réussie et que son intégration socioculturelle en Suisse n'est pas exceptionnelle, son comportement, les conséquences pour lui et ses enfants d'un refus de demeurer en Suisse, son âge (34 ans) ainsi que ses possibilités de réinsertion au Sénégal, pays dans lequel résident des membres de sa famille. C'est partant à bon droit que le Tribunal administratif fédéral a confirmé le refus d'approuver la prolongation de l'autorisation de séjour du recourant.
6.
Les considérants qui précèdent conduisent au rejet du recours. Succombant, le recourant doit supporter les frais judiciaires (art. 66 al. 1 LTF). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

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.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations, au Tribunal administratif fédéral, Cour VI, ainsi qu'au Service de la population du canton de Vaud.
Lausanne, le 31 mars 2017
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber