Faits :
A.
A.a. A._, ressortissant nord-africain né en 1990, sans titre de séjour en Suisse et sous le coup d'une expulsion judiciaire jusqu'en 2028, a été appréhendé le 28 novembre 2021 à Genève. Il lui est reproché d'avoir, ce jour-là, dérobé un smartphone de modèle IPhone, un haut-parleur sans fil et un flacon de parfum Hugo Boss dans une automobile en stationnement. La police l'a interpellé peu après qu'il se fut éloigné de "quelque 5 m." du véhicule. Elle a retrouvé sur lui, outre les objets précités, un téléphone portable, une montre et une bague, objets que l'automobiliste n'a pas identifiés comme lui appartenant.
Après avoir refusé de s'exprimer devant la police - sauf pour l'autoriser à avertir son amie "Mme B._" -, A._ a admis les faits lors de sa comparution devant le Ministère public de la République et canton de Genève (ci-après : le Ministère public); le prévenu a également déclaré fréquenter les associations qui, comme Caritas, aidaient les gens dans sa situation et souhaiter regagner son pays d'origine où se trouvaient ses documents d'identité.
A la suite de la demande de mise en détention du Ministère public, A._ a expliqué, devant le Tribunal des mesures de contrainte (ci-après : Tmc), vouloir retourner vivre chez sa copine "B.B._", dont il ignorait le nom de famille, mais qui habitait à Genève à une adresse qu'il ne souhaitait pas divulguer. Par ordonnance du 29 novembre 2021, le Tmc a ordonné le placement en détention provisoire de A._ pour trois mois, retenant l'existence de charges suffisantes (vol [<ref-law>] et rupture de ban [<ref-law>]), ainsi que des risques de fuite et de réitération.
A.b. Deux autres procédures - dont la jonction a été annoncée par le Ministère public - sont ouvertes à l'encontre de A._ dans le canton de Genève.
Dans son casier judiciaire suisse - où A._ figure sous quatre alias -, sont inscrites cinq condamnations pour infractions au droit des étrangers, le cas échéant en concours avec des violations de domicile, des vols (dont une fois par métier), des dommages à la propriété et des contraventions à la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (RS 812.121; LStup).
B.
Le 22 décembre 2021, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours intenté par A._ contre l'ordonnance du Tmc du 29 novembre 2021. Elle a également rejeté la demande d'assistance judiciaire pour la procédure de recours, refusant en conséquence d'indemniser le défenseur d'office de A._; les frais, arrêtés à 900 fr. ont été mis à la charge du précité.
C.
Par acte du 24 janvier 2022, A._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant à son annulation, à sa libération immédiate, à la constatation de la violation de l'art. 6 par. 3 let. c CEDH et à l'octroi de l'assistance judiciaire pour la procédure cantonale de recours. A titre subsidiaire, il demande sa libération immédiate, assortie de toute mesure de substitution jugée utile et nécessaire, la constatation de la violation de l'art. 6 par. 3 let. c CEDH et le renvoi de la cause à l'autorité précédente pour nouvelle décision sur la question de l'assistance judiciaire au sens des considérants. Le recourant sollicite également l'octroi de l'assistance judiciaire pour la procédure fédérale.
Le Ministère public a conclu au rejet du recours, sans formuler d'observation. L'autorité précédente a renoncé à déposer des déterminations. Le 8 février 2022, le recourant a persisté dans ses conclusions.

Considérant en droit :
1.
Le recours en matière pénale (<ref-law>) est ouvert contre une décision relative à la détention provisoire ou pour des motifs de sûreté au sens des <ref-law>. Selon l'art. 81 al. 1 let. a et b ch. 1 LTF, le recourant, prévenu détenu, a qualité pour recourir. Le recours a été formé en temps utile (<ref-law>) contre une décision rendue par une autorité statuant en tant que dernière instance cantonale (<ref-law>) et les conclusions présentées sont recevables au regard de l'<ref-law>. Il y a donc lieu d'entrer en matière.
2.
Le recourant conteste tout d'abord l'existence de charges suffisantes. A cet égard, il soutient que les faits reprochés devraient être qualifiés de tentative de vol, dès lors qu'il se trouvait "à moins de 5 mètres" du véhicule concerné; il s'agirait en tout état de cause d'une contravention vu la valeur inférieure à 300 fr. des objets litigieux (vol d'importance mineure au sens de l'<ref-law>; <ref-ruling> consid. 3.1 p. 133 s.), ce qui ne constituerait pas des charges permettant un placement en détention. Selon le recourant, tel ne pourrait pas non plus être le cas de la rupture de ban, seule infraction qui pourrait dès lors entrer en considération; ce chef de prévention ne permettrait en effet pas un placement en détention lorsque les autorités n'ont pris aucune mesure pour exécuter la décision d'expulsion, ce qui serait le cas en l'espèce.
2.1. Une mesure de détention provisoire n'est compatible avec la liberté personnelle garantie aux art. 10 al. 2 Cst. et 5 CEDH que si elle repose sur une base légale (art. 31 al. 1 et art. 36 al. 1 Cst.), soit en l'espèce l'<ref-law>. Elle doit en outre correspondre à un intérêt public et respecter le principe de la proportionnalité (art. 36 al. 2 et 3 Cst., 197 al. 1 let. c et d, 212 al. 3, 237 al. 1 et 2 CPP). Pour que tel soit le cas, la privation de liberté doit être justifiée par un risque de fuite ou par un danger de collusion ou de réitération (art. 221 al. 1 let. a, b et c CPP). Préalablement à ces conditions, il doit exister des charges suffisantes, soit de sérieux soupçons de culpabilité, à l'égard de l'intéressé (<ref-law>; art. 5 par. 1 let. c CEDH; <ref-ruling> consid. 2 p. 187 s).
Selon la jurisprudence, il n'appartient pas au juge de la détention de procéder à une pesée complète des éléments à charge et à décharge et d'apprécier la crédibilité des personnes qui mettent en cause le prévenu. Il doit uniquement examiner s'il existe des indices sérieux de culpabilité justifiant une telle mesure. L'intensité des charges propres à motiver un maintien en détention préventive n'est pas la même aux divers stades de l'instruction pénale; si des soupçons, même encore peu précis, peuvent être suffisants dans les premiers temps de l'enquête, la perspective d'une condamnation doit apparaître avec une certaine vraisemblance après l'accomplissement des actes d'instruction envisageables (<ref-ruling> consid. 2.1 p. 333 s.; 316 consid. 3.1 et 3.2 p. 318 s.).
En matière de détention provisoire, la Directive 2008/115/CE du Parlement européen et du Conseil du 16 décembre 2008 relative aux normes et procédures communes applicables dans les Etats membres au retour des ressortissants de pays tiers en séjour irrégulier (ci-après : Directive sur le retour) - en tant que développement de l'acquis de Schengen (cf. l'Arrêté fédéral portant approbation et mise en oeuvre de l'échange de notes du 30 janvier 2009 entre la Suisse et la Communauté européenne concernant la reprise de la Directive CE 2008/115/CE sur le retour; RS 0.362.380.042; JO L 348 du 24 décembre 2008 p. 98; RO 2010 5925; <ref-ruling> consid. 1.2 p. 236) - ne s'applique pas (respectivement, peut ne pas s'appliquer) lorsque d'autres délits que le séjour irrégulier sont retenus à l'encontre du prévenu (<ref-ruling> consid. 2.4 p. 267 s. et les arrêts cités).
2.2. La cour cantonale a en substance retenu que le vol effectué par le recourant lors de son interpellation était achevé : le recourant se trouvait à l'extérieur du véhicule en possession de trois objets mobiliers, dont un IPhone dont la valeur était notoirement supérieure à 300 fr.; dès lors que le recourant était sans emploi et déclarait vivre de l'aide caritative, il s'imposait de considérer qu'il était déterminé, par avance, à s'emparer du plus gros butin possible qu'il trouverait dans le véhicule. Selon la juridiction précédente, ces éléments fondaient à eux seuls des charges suffisantes en lien avec l'<ref-law>. La cour cantonale a ensuite relevé que le recourant ne contestait pas avoir séjourné illégalement en Suisse en parallèle des faits susmentionnés; il n'était ainsi pas poursuivi uniquement pour rupture de ban et la Directive sur le retour ne s'appliquait donc pas (cf. consid. 2.5 p. 4 s. de l'arrêt attaqué).
2.3. Ce raisonnement ne prête pas le flanc à la critique. Peu importe tout d'abord de déterminer à quelle distance du véhicule se trouvait le recourant. En effet, à ce stade de la procédure, il semble incontesté qu'au moment de son interpellation, il se trouvait à l'extérieur de cette voiture (cf. le rapport de police du 29 novembre 2021 cité par le recourant); il était alors en possession de trois objets mobiliers, qui y avaient été dérobés, ce qu'il ne conteste pas (cf. notamment ad p. 12 du recours). Il n'apparaît pas non plus arbitraire de retenir que la valeur totale des objets - certes peut-être qualifiés de "vieux" par la partie plaignante (cf. son audition du 28 novembre 2021 p. 2) - puisse être supérieure à 300 fr. vu l'IPhone entrant en considération. En tout état de cause, le recourant ne développe aucune argumentation afin de démontrer qu'il entendait limiter ses actes à des éléments patrimoniaux de faible valeur (cf. sur l'intention en lien avec l'<ref-law>, <ref-ruling> consid. 1a p. 156, 122 IV 156 consid. 2 p. 160, arrêt 6B_497/2020 du 3 novembre 2020 consid. 2.1.2). Dans le cadre de l'examen des charges suffisantes qui prévaut en matière de détention provisoire, ces éléments suffisent en l'état pour écarter l'hypothèse d'une tentative de vol ou d'un vol d'importance mineure - arguments que le recourant pourra, le cas échéant, faire valoir devant le juge du fond - et pour retenir que l'infraction de vol au sens de l'<ref-law> entre en considération dans le cas d'espèce (sur cette disposition, arrêts 6B_1052/2020 du 19 juillet 2021 consid. 4.1; 6B_943/2020 du 19 janvier 2021 consid. 2.4.1; 6B_1360/2019 du 20 novembre 2020 consid. 2.3; sur les conditions de cette infraction voir également DUPUIS ET AL., Petit commentaire, Code pénal, 2e éd. 2017, nos 5 ss ad <ref-law>).
Dès lors que le recourant n'est pas uniquement mis en cause pour rupture de ban au sens de l'<ref-law>, celui-ci ne peut pas se voir libérer en application de la Directive sur le retour et il n'y a pas lieu d'examiner ses griefs en lien avec le prétendu défaut de mesures entreprises par les autorités pour mettre en oeuvre son renvoi.
3.
Le recourant conteste ensuite l'existence d'un risque de fuite.
3.1. Le risque de fuite au sens de l'<ref-law> doit s'analyser en fonction d'un ensemble de critères tels que le caractère de l'intéressé, sa moralité, ses ressources, ses liens avec l'État qui le poursuit ainsi que ses contacts à l'étranger, qui font apparaître le risque de fuite non seulement possible, mais également probable. La gravité de l'infraction ne peut pas, à elle seule, justifier la prolongation de la détention, même si elle permet souvent de présumer un danger de fuite en raison de l'importance de la peine dont le prévenu est menacé (<ref-ruling> consid. 2.2 p. 507 et les arrêts cités).
3.2. En l'occurrence, le recourant, ressortissant étranger sans emploi, ne conteste pas ne pas disposer d'un titre de séjour en Suisse et être sous le coup d'une décision d'expulsion entrée en force. Dans une telle configuration, l'avenir en Suisse du recourant paraît fortement compromis. Le recourant ne donne pas non plus d'indication sur le lieu où, selon les affirmations de son amie, il résiderait à Genève (cf. l'attestation - non datée - de celle-ci produite devant la cour cantonale). En tout état de cause, les liens avec la Suisse dont se prévaut le recourant - soit une relation amoureuse - semblent pour le moins ténus dès lors que, comme l'a retenu l'autorité précédente, son amie est domiciliée en France (cf. également l'attestation précitée). Indépendamment de ce qui pourrait avoir prévalu à ce jour - tant dans le cadre de cette relation que par rapport à de précédentes convocations judiciaires -, le recourant pourrait dès lors être tenté de se rendre à ce domicile français et/ou d'entrer dans la clandestinité afin de se soustraire aux différentes procédures judiciaires suisses dont il est l'objet, respectivement aux peines privatives de liberté qui pourraient être prononcées à son encontre. La cour cantonale pouvait ainsi, sans violer le droit fédéral, retenir l'existence d'un danger de fuite.
3.3. Conformément au principe de la proportionnalité ancré à l'art. 36 al. 3 Cst., il convient d'examiner les possibilités de mettre en oeuvre d'autres solutions moins dommageables que la détention (règle de la nécessité). Cette exigence est concrétisée par l'<ref-law>, qui prévoit que le tribunal compétent ordonne une ou plusieurs mesures moins sévères en lieu et place de la détention si ces mesures permettent d'atteindre le même but que la détention.
En cas de risque de fuite, une obligation de passage hebdomadaire à un poste de police n'est pas de nature à empêcher une personne de s'enfuir à l'étranger ou de passer dans la clandestinité (<ref-ruling> consid. 3.2 p. 510). On ne voit pas non plus en quoi l'élection de domicile en l'étude de sa mandataire assurerait la présence du recourant en Suisse. Au vu de ces éléments, aucune mesure de substitution ne permet de prévenir le danger de fuite existant et ce grief peut être rejeté.
3.4. Le recourant ne développe, à juste titre, aucune argumentation tendant à démontrer que la durée de la détention provisoire violerait le principe de proportionnalité, notamment eu égard à la peine concrètement encourue (cf. consid. 5 p. 5 s. de l'arrêt attaqué).
3.5. Au vu des considérations précédentes, la Chambre pénale de recours pouvait, sans violer le droit fédéral, confirmer le placement en détention ordonné par le Tmc.
4.
Invoquant une violation de l'art. 6 par. 3 let. c CEDH, le recourant, au bénéfice d'une défense d'office dans le cadre de l'instruction ouverte à son encontre (cf. la décision de nomination d'avocat d'office du 29 novembre 2021 en lien avec l'art. 132 al. 1 let. b, 2 et 3 CPP), reproche à l'autorité précédente de lui avoir refusé une telle défense pour la procédure de recours au motif que son recours cantonal aurait été dénué de chances de succès (sur cette notion en lien avec l'assistance judiciaire, <ref-ruling> consid. 9.1 p. 537; <ref-ruling> consid. 1.2 p. 397; <ref-ruling> consid. 2.3.1 p. 135 s.; arrêt 1B_591/2021 du 12 janvier 2022 consid. 2.1).
4.1. La cour cantonale a estimé que la contestation des charges soulevée par le recourant reposait, pour l'essentiel, sur une lecture erronée (i) de la jurisprudence et (ii) des principes juridiques applicables à la théorie de l'infraction pénale, à la Directive sur le retour, aux éléments constitutifs du vol simple et d'importance mineure, ainsi qu'au pouvoir d'examen de l'autorité de recours en matière de détention provisoire; les arguments développés devant l'instance de recours étaient donc d'emblée voués à l'échec, ce qui permettait de refuser la prise en charge des honoraires du défenseur d'office du recourant (cf. consid. 6.2 p. 6 de l'arrêt attaqué).
4.2. Ce raisonnement - certes sévère - relatif à l'absence de chances de succès du recours cantonal peut être confirmé.
En effet, la désignation d'un conseil d'office pour la procédure pénale principale n'est pas un blanc-seing pour introduire des recours aux frais de l'Etat, y compris contre des décisions de détention provisoire (<ref-ruling> consid. 3.3.1 p. 214; arrêts 1B_516/2020 du 3 novembre 2020 consid. 5.1; 1B_164/2017 du 15 août 2017 consid. 2 et l'arrêt cité). Il appartenait en conséquence au recourant de développer une argumentation, même brève, permettant de comprendre en quoi son recours cantonal aurait pu, le cas échéant, aboutir, ce qu'il ne fait pas. En tout état de cause, le fait que le refus d'octroyer une défense d'office pour la procédure de recours soit intervenu à la suite d'un placement initial en détention avant jugement - et non pas d'une prolongation de cette mesure - et/ou que le recourant rappelle avoir remis en cause l'ensemble des conditions de la détention provisoire (charges suffisantes, risque de fuite, mesures de substitution, proportionnalité de la mesure) ne suffisent pas en soi pour démontrer l'existence de chances de succès sur le fond, notamment par rapport à l'un des points précités en lien avec la jurisprudence applicable dans le cas d'espèce (cf. au demeurant consid. 2.1 et 2.3 ci-dessus).
5.
Il s'ensuit que le recours est rejeté.
Le recourant a demandé l'octroi de l'assistance judiciaire pour la procédure fédérale (<ref-law>). Son recours visait notamment le refus de lui accorder une défense d'office pour la procédure cantonale de recours. Dans cette mesure, son recours fédéral n'était pas d'emblée dénué de chances de succès et cette requête doit être admise. Il y a lieu de désigner Me Magali Buser en tant qu'avocate d'office du recourant pour la procédure fédérale et de lui allouer une indemnité à titre d'honoraires, qui seront supportés par la caisse du Tribunal fédéral. Il n'est pas perçu de frais judiciaires (<ref-law>), ni alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La demande d'assistance judiciaire est admise. Me Magali Buser est désignée comme avocate d'office du recourant et une indemnité de 1'500 fr. lui est allouée à titre d'honoraires, à payer par le Tribunal fédéral. Il n'est pas perçu de frais judiciaires.
3.
Le présent arrêt est communiqué à la mandataire du recourant, au Ministère public de la République et canton de Genève et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 11 février 2022
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant : Chaix
La Greffière : Kropf