Faits:
A.
Le 23 avril 2013, X._ a été arrêté par la police genevoise, prenant alors connaissance de la procédure pénale ouverte à son encontre par le Ministère public de la République et canton de Genève - représenté depuis mars 2012 par le Procureur Y._ - pour fraude dans la saisie, voire diminution de l'actif au préjudice des créanciers (cause xxx). A cette même date, ont eu lieu des perquisitions à son domicile, ainsi que dans ses locaux professionnels.
Par fax du 23 avril 2013, X._ a requis sa mise en liberté immédiate et demandé au Procureur Y._ de se dessaisir de la cause xxx. A l'appui de cette seconde requête, le prévenu a expliqué que le magistrat avait été avocat-stagiaire, puis collaborateur dans l'étude où travaillait Me Z._. Or, ce dernier représentait la partie plaignante dans une précédente procédure pénale intentée à son encontre, à la suite de laquelle il avait été condamné.
Après avoir transmis cette requête à la Chambre pénale de recours de la C our de justice de la République et canton de Genève, le Ministère public s'y est opposé. Il a confirmé avoir effectué son stage (de septembre 2007 à septembre 2008) dans l'étude où Me Z._ avait exercé jusqu'au 1er mai 2009 et y avoir ensuite travaillé comme collaborateur, puis associé (de janvier 2009 à décembre 2011). Selon les informations figurant dans le système informatique judiciaire, la procédure pénale dans laquelle Me Z._ intervenait contre X._ avait débuté le 7 mai 2008 et s'était achevée le 15 février 2010. Le Procureur a encore précisé ne pas se souvenir si l'affaire en question avait été évoquée à l'époque. Quant aux actes d'instruction entrepris dans la procédure pénale xxx - perquisitions et arrestation du requérant -, ils étaient, selon le magistrat, justifiés par la récolte d'informations sur les comptes bancaires où se trouvaient les montants que le prévenu était soupçonné d'avoir envoyé à l'étranger et par un risque de collusion. X._ a persisté dans ses conclusions, relevant le caractère médiatisé de l'affaire pénale défendue par Me Z._.
B.
Le 3 juillet 2013, la Chambre pénale de recours a rejeté la requête de récusation au motif que les circonstances d'espèce (absence de participation audit dossier, départ de l'étude de Me Z._ un an avant l'achèvement de la procédure pénale et défaut d'élément concret indiquant une connaissance par le Procureur de cette affaire à l'époque) n'étaient objectivement pas suffisantes pour retenir une apparence de prévention. La cour cantonale a en outre relevé que l'aspect médiatique de cette procédure - alors close - était dénué de pertinence et que les mesures prises par le Ministère public dans la cause xxx ne constituaient pas des violations graves dénotant une intention de nuire.
C.
Par mémoire du 9 septembre 2013, X._ forme un recours en matière pénale, concluant à l'annulation de l'arrêt cantonal, à la récusation du Procureur et, subsidiairement, au renvoi de la cause à l'autorité cantonale pour qu'elle statue au sens des considérants.
Invités à se déterminer, le Ministère public a conclu au rejet du recours, renvoyant aux observations déposées devant l'instance précédente, tandis que cette dernière s'est référée à ses considérants, sans formuler de détermination complémentaire. Le 23 octobre 2013, le recourant a persisté dans ses conclusions.

Considérant en droit:
1.
Conformément aux art. 78 et 92 al. 1 LTF, une décision incidente relative à la récusation d'un magistrat pénal peut faire immédiatement l'objet d'un recours en matière pénale. Le recourant, qui a formulé la requête de récusation, a qualité pour recourir (<ref-law>). Il a agi dans le délai de trente jours (art. 100 al. 1 et 46 al. 1 LTF) contre une décision rendue en dernière instance cantonale (<ref-law>).
2.
Le recourant se plaint d'une violation des art. 56 let. f CPP, 30 al. 1 Cst. et 6 § 1 CEDH. Il soutient que le partage des bureaux par le représentant du Ministère public et par Me Z._ - alors mandaté par la partie plaignante dans la procédure pénale où lui-même était prévenu - ferait naître un doute quant à l'impartialité du magistrat, qui par ailleurs ne pouvait avoir ignoré cette affaire en raison de son retentissement médiatique. Selon le recourant, les mesures "drastiques et inexplicables" prises dans la procédure xxx viendraient confirmer l'apparence de prévention du Procureur à son égard.
2.1. La garantie d'un tribunal indépendant et impartial résultant des art. 30 al. 1 Cst. et 6 § 1 CEDH - qui ont, de ce point de vue, la même portée - permet d'exiger la récusation d'un juge dont la situation ou le comportement est de nature à susciter des doutes quant à son impartialité. Elle vise à éviter que des circonstances extérieures à l'affaire puissent influencer le jugement en faveur ou au détriment d'une partie. Elle n'impose pas la récusation seulement lorsqu'une prévention effective du juge est établie, car une disposition interne de sa part ne peut guère être prouvée; il suffit que les circonstances donnent l'apparence de la prévention et fassent redouter une activité partiale du magistrat. Cependant, seules les circonstances objectivement constatées doivent être prises en considération; les impressions purement individuelles d'une des parties au procès ne sont pas décisives (<ref-ruling> consid. 5.1 p. 125 s.; III 120 consid. 3.2.1 p. 124; <ref-ruling> consid. 2.2 p. 3; IV 142 consid. 2.1 p. 144 s. et les arrêts cités). Les motifs de récusation mentionnés à l'<ref-law> concrétisent ces garanties. Ils imposent en particulier la récusation d'un magistrat lorsque d'autres motifs, notamment un rapport d'amitié étroit ou d'inimitié avec une partie ou son conseil, sont de nature à le rendre suspect de prévention (let. f). Cette disposition a la portée d'une clause générale recouvrant tous les motifs de récusation non expressément prévus aux lettres a à e de l'<ref-law> (<ref-ruling> consid. 4.2.1 p. 428; IV 142 consid. 2.1 p. 144).
Pour être à même de trancher un différend avec impartialité, un juge ne doit pas se trouver dans la sphère d'influence des parties. Un rapport de dépendance, voire des liens particuliers (amitié ou inimitié), entre le juge et une personne intéressée à l'issue de la procédure - telle qu'une partie ou son mandataire - peut constituer un motif de récusation dans des circonstances spéciales qui ne peuvent être admises qu'avec retenue; il faut qu'il y ait un lien qui, par son intensité et sa qualité, soit de nature à faire craindre objectivement qu'il influence le juge dans la conduite de la procédure et dans sa décision (<ref-ruling> consid. 5.1 p. 125 s.; <ref-ruling> consid. 2.4 p. 5; arrêt 1B_199/2012 du 13 juillet 2012 consid. 5.1 et les références citées). Ainsi, un avocat qui exerce les fonctions de juge apparaît objectivement partial non seulement lorsque, dans le cadre d'une autre procédure, il représente ou a représenté l'une des parties à la procédure dans laquelle il siège, mais également lorsqu'il représente ou a représenté récemment la partie adverse de cette partie (<ref-ruling> consid. 5.1 p. 126; III 120 consid. 3.2.1 p. 124; <ref-ruling> consid. 5.3 p. 407 s.; <ref-ruling> consid. 4.1 à 4.3 p. 15 ss). En revanche, un juge n'est pas récusable du simple fait qu'il aurait précédemment représenté des intérêts opposés à la partie en cause (ATF <ref-ruling> consid. 2.3 p. 4 concernant un magistrat précédemment avocat de l'ASLOCA). Il n'y a pas non plus lieu de requérir la récusation d'un membre d'un tribunal du seul fait que l'avocat d'une des parties exerce, dans d'autres causes, en tant que juge suppléant au sein de cette même autorité ou d'une instance de recours, sauf en cas de circonstances spécifiques fondant une apparence de prévention et un risque de parti pris de la part d'un des membres du tribunal (<ref-ruling> consid. 5.4 p. 127 ss; <ref-ruling> consid. 6.4.2 à 6.4.4 p. 7 s.)
2.2. Dans la phase de l'enquête préliminaire et de l'instruction, les principes applicables à la récusation du ministère public sont ceux qui ont été dégagés à l'égard des juges d'instruction avant l'introduction du Code de procédure pénale. Selon l'<ref-law>, le ministère public est l'autorité investie de la direction de la procédure jusqu'à la mise en accusation. A ce titre, il doit veiller au bon déroulement et à la légalité de la procédure (<ref-law>). Durant l'instruction il doit établir, d'office et avec un soin égal, les faits à charge et à décharge (<ref-law>); il doit statuer sur les réquisitions de preuves et peut rendre des décisions quant à la suite de la procédure (classement ou mise en accusation), voire rendre une ordonnance pénale pour laquelle il assume une fonction juridictionnelle. Dans ce cadre, le ministère public est tenu à une certaine impartialité même s'il peut être amené, provisoirement du moins, à adopter une attitude plus orientée à l'égard du prévenu ou à faire état de ses convictions à un moment donné de l'enquête. Cela est en particulier le cas lorsqu'il décide de l'ouverture d'une instruction (qui suppose l'existence de soupçons suffisants au sens de l'<ref-law>) ou lorsqu'il ordonne des mesures de contrainte. Tout en disposant, dans le cadre de ses investigations, d'une certaine liberté, le magistrat reste tenu à un devoir de réserve. Il doit s'abstenir de tout procédé déloyal, instruire tant à charge qu'à décharge et ne point avantager une partie au détriment d'une autre (<ref-ruling> consid. 2.2.1 p. 145 et les arrêts cités).
Selon la jurisprudence, des erreurs de procédure ou d'appréciation commises par le juge ne suffisent pas à fonder objectivement un soupçon de prévention, à moins qu'elles soient particulièrement lourdes ou répétées et qu'elles constituent des violations graves de ses devoirs qui dénotent une intention de nuire (<ref-ruling> consid. 2.3 p. 146 et les arrêts cités).
2.3. En l'espèce, il n'est pas contesté que le Procureur intimé travaillait en tant qu'avocat-stagiaire, puis comme collaborateur dans l'étude où exerçait Me Z._, alors mandataire de la partie plaignante lors de la première procédure pénale dirigée contre le recourant. Il s'agit de déterminer si le partage de locaux suffit pour retenir une apparence de prévention du magistrat pénal dans la seconde procédure. Un tel élément peut effectivement venir renforcer un soupçon de partialité existant (cf. le jugement Wettstein c/ Suisse du 21 décembre 2000, Recueil CEDH 2000-XII s. 403 ch. 45 et 48 où la juge prévenue - qui exerçait en parallèle en tant qu'avocate dans une procédure pendante contre le requérant - partageait de surcroît ses bureaux avec le mandataire d'un autre adversaire du requérant), mais tel n'est pas le cas en l'espèce, faute notamment d'autres circonstances objectives.
En effet, à l'époque de la première affaire, le Procureur n'était pas, ainsi que l'a constaté la cour cantonale, le mandataire de la partie plaignante et il n'a pas non plus été démontré qu'il aurait participé à ce dossier ou qu'il en aurait eu connaissance; le recourant n'invoque d'ailleurs pas l'<ref-law> à l'appui de sa requête. Cette cause a de plus continué d'être traitée par Me Z._ après son départ de l'étude en mai 2009 jusqu'à sa clôture en février 2010. Quant au caractère médiatisé allégué de cette affaire - qui, selon le recourant, démontrerait que le Procureur aurait dû faire le lien entre les deux affaires le mettant en cause -, il y a lieu de constater qu'il découle de la "relative célébrité de la plaignante" (cf. ses observations du 7 mai 2013) et non de l'identité du recourant, qui n'a d'ailleurs pas soutenu avoir été lui-même - notamment de manière nominative - à l'origine du possible écho médiatique résultant de ce dossier. Les deux procédures pénales concernant le recourant ne sont en outre pas simultanées, puisque la première s'est terminée en février 2010 et que la seconde n'a été ouverte qu'à la suite d'une plainte pénale déposée en septembre 2011 (cf. a contrario l'arrêt Wettstein précité). Entre mai 2009 (départ de Me Z._) et la reprise de l'instruction de la cause xxx par le représentant intimé du Ministère public (mars 2012), il s'est donc écoulé près de trois ans. La partie plaignante dans la seconde cause n'est au demeurant pas la même que celle qui avait déposé la première plainte pénale contre le recourant. Ce dernier ne prétend enfin pas que les faits qui lui sont reprochés ce jour relèveraient de la même problématique que ceux qui lui ont valu la première condamnation. Il n'existe donc aucune autre circonstance concrète qui permettrait de craindre que le Procureur puisse être influencé dans la présente procédure.
Une possible prévention ne résulte pas non plus de l'absence alléguée de justification des mesures prises à l'encontre du recourant (arrestation et double perquisition), dès lors que lui-même ne les mentionne qu'à titre d'indices supplémentaires. Ce faisant, il reconnaît que ces éléments ne suffisent pas à eux seuls pour mettre en cause l'impartialité du Ministère public intimé; il peut d'ailleurs être précisé que le recourant a été remis en liberté le lendemain de son arrestation. Au demeurant, de tels actes sont inhérents à l'exercice de la charge du magistrat et il appartient, cas échéant, aux juridictions de recours compétentes de constater et/ou redresser d'éventuelles erreurs (<ref-law>; <ref-ruling> consid. 2.3 p. 146; <ref-ruling> consid. 3a p. 138; arrêt 1B_205/2013 du 9 août 2013 consid. 3.1).
Partant, la Chambre pénale de recours n'a pas violé le droit fédéral en rejetant la requête de récusation déposée par le recourant.
3.
Il s'ensuit que le recours est rejeté. Le recourant qui succombe supporte les frais de la présente procédure (<ref-law>).

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 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 29 octobre 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Kropf