Faits :
A.
Dans le cadre de l'instruction menée à son encontre depuis le 3 novembre 2014, A._ a été entendu le 24 septembre 2015 par le Procureur Bertrand Bühler. En raison de propos tenus par ce dernier à son sujet, le prévenu a demandé sa récusation; cette requête a été rejetée le 19 octobre 2015 par la Chambre des recours pénale du Tribunal cantonal vaudois. Le 5 janvier 2016, le Tribunal fédéral a admis le recours intenté par A._ contre cette décision (cause 1B_430/2015). Selon le chiffre 1 du dispositif de cet arrêt, la cause a été renvoyée à l'autorité précédente pour nouvelle décision sur les frais et dépens de la procédure cantonale.
B.
Le Procureur général du canton de Vaud a pris acte de cette décision le 28 janvier 2016 et s'en est remis à justice s'agissant d'une éventuelle indemnité. Ce même jour, A._ a conclu au paiement d'une indemnité de 4'594 fr. 90, montant correspondant aux opérations effectuées dans le cadre de la procédure de récusation. Il s'est encore déterminé les 29 janvier et 2 février 2016.
Le 12 février 2016, la Chambre des recours pénale a mis les frais judiciaires de la décision annulée, ceux de sa seconde décision, ainsi que les indemnités allouées au défenseur d'office du prévenu (777 fr. 60 pour la première procédure et 97 fr. 20 pour la seconde) à la charge de l'Etat. Quant à l'octroi d'une indemnité, la cour cantonale a rappelé qu'en principe, elle renvoyait la partie ayant obtenu gain de cause à agir à la fin de la procédure; dès lors toutefois que le mandataire de A._ intervenait en tant qu'avocat d'office, elle a retenu que son client ne pouvait pas prétendre à l'allocation d'une indemnité au sens de l'<ref-law>.
C.
Par acte du 18 mars 2016, A._ forme un recours en matière pénale contre ce jugement, concluant à sa réforme en ce sens qu'une indemnité de dépens de 4'594 fr. 90 lui soit allouée pour la procédure cantonale de récusation. A titre subsidiaire, il demande le renvoi de la cause à l'autorité précédente. Il dépose également un recours constitutionnel subsidiaire, demandant l'annulation de l'arrêt attaqué et le renvoi de la cause pour nouvelle décision. Il sollicite aussi l'octroi de l'assistance judiciaire.
Invités à se déterminer, le Procureur général s'en est remis à justice et l'autorité précédente a renoncé à déposer des observations.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement les conditions de recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2 p. 59).
1.1. Le recours contre une décision traitant des frais et des dépens en instance cantonale est en principe soumis à la même voie de droit que celle qui est ouverte contre la décision sur le fond du litige (<ref-ruling> consid. 1.1 p. 160; arrêt 1B_575/2011 du 29 février 2012 consid. 1). En l'espèce, le litige initial portait sur une demande de récusation d'un magistrat dans le cadre d'une procédure pénale. Partant, l'arrêt attaqué peut faire l'objet d'un recours en matière pénale (<ref-law>), voie de droit qui permet d'invoquer notamment toute violation du droit fédéral, y compris des droits constitutionnels (<ref-law>).
Le recours constitutionnel subsidiaire est donc exclu. Il est au demeurant douteux que l'argumentation développée à cet égard soit suffisante vu les exigences de motivation en la matière (art. 42 al. 2, 116, 106 al. 2 par renvoi de l'<ref-law>; <ref-ruling> consid. 3 p. 237).
1.2. L'arrêt - sur renvoi du Tribunal fédéral - statue sur les frais et dépens pour la procédure cantonale de récusation. Il ne met donc pas fin à la procédure pénale et revêt un caractère incident.
1.2.1. Si l'<ref-law> permet le recours immédiat au Tribunal fédéral contre les décisions incidentes sur la compétence et la récusation, cette voie ne s'applique pas lorsque seule la question des frais et dépens est contestée et la recevabilité se détermine dès lors au regard de l'<ref-law> (<ref-ruling> consid. 2.2 et 2.3 p. 95 s.).
1.2.2. Selon l'<ref-law>, le recours en matière pénale n'est recevable, contre des décisions incidentes, que si celles-ci sont susceptibles de causer un préjudice irréparable à leur destinataire (let. a) ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (let. b); cette dernière hypothèse n'entre manifestement pas en considération en l'espèce. En matière pénale, le préjudice irréparable au sens de l'<ref-law> se rapporte à un dommage de nature juridique qui ne puisse pas être réparé ultérieurement par un jugement final ou une autre décision favorable au recourant (<ref-ruling> consid. 2.2 p. 287). Cette réglementation est fondée sur des motifs d'économie de procédure. En tant que cour suprême, le Tribunal fédéral doit en principe ne s'occuper qu'une seule fois d'un procès et cela seulement lorsqu'il est certain que le recourant subit effectivement un dommage définitif (<ref-ruling> consid. 1 p. 115).
Selon la jurisprudence, le prononcé accessoire sur les frais et dépens, contenu dans une décision incidente - par exemple de renvoi -, n'est pas de nature à causer un préjudice irréparable au sens de l'<ref-law> (<ref-ruling> consid. 1.2 p. 47; <ref-ruling> consid. 1.2.2 p. 333 s.). Il peut faire l'objet d'un recours immédiat au Tribunal fédéral uniquement dans le cadre d'un recours intenté contre le point principal traité dans la décision incidente à supposer qu'une telle voie de droit soit ouverte en application des art. 92 ou 93 al. 1 LTF. A défaut, il n'est possible de contester la seule question de la répartition des frais et dépens que dans un recours contre la décision finale (cf. <ref-law>; <ref-ruling> consid. 2.3 p. 95 s.; <ref-ruling> consid. 1.2.2 p. 333 s.; arrêt 1B_51/2013 du 27 septembre 2013 consid. 1.2). Si la décision finale n'est pas contestée sur le point principal, la voie du recours direct au Tribunal fédéral est ouverte pour faire trancher la question accessoire restée litigieuse (<ref-ruling> consid. 1.1 p. 59; <ref-ruling> consid. 1.2.1 p. 332; <ref-ruling> consid. 2.2 p. 648).
En vertu de l'<ref-law>, il incombe au recourant d'alléguer les faits qu'il considère comme propres à fonder sa qualité pour recourir et ceux permettant de démontrer l'existence d'un préjudice irréparable lorsque celui-ci n'est pas d'emblée évident (<ref-ruling> consid. 2.3 p. 287).
1.2.3. En l'occurrence, la décision attaquée statue uniquement sur le point - accessoire - des frais et dépens, la question - principale - relative à la récusation ayant été tranchée définitivement par le Tribunal fédéral. Si la situation diffère quelque peu de celles évoquées dans les arrêts susmentionnés, il n'y a cependant aucune raison de s'écarter de la solution qui y est retenue. L'arrêt entrepris ne cause donc en principe aucun préjudice irréparable au recourant et doit être attaqué avec la décision finale (<ref-law>). Le recourant ne prétend d'ailleurs pas que son éventuel dommage - en l'état purement économique - ne pourra pas être réparé par une décision ultérieure. Contrairement de plus à ce qu'il soutient, la cour cantonale lui a reconnu, sur le principe, le droit à une indemnité pour la procédure de récusation. Si aucun montant ne lui a été accordé à ce titre, c'est en raison de la défense d'office dont il bénéficie, ce qui est conforme à la jurisprudence (<ref-ruling> consid. 1 p. 206).
Certes, le recourant prétend en substance que l'indemnité allouée à son mandataire d'office (777 fr. 60) ne couvrirait pas les démarches effectuées entre le 24 septembre et le 8 octobre 2015, soit préalablement à la décision d'octroi d'assistance judiciaire du 9 octobre 2015. Si tel devait être le cas, on ne voit pas ce qui l'empêcherait de déposer ou de réitérer ses conclusions devant le juge du fond et/ou de contester l'arrêt entrepris avec la décision finale rendue par ce dernier. Cela vaut d'autant plus que le juge du fond doit examiner la question de la date des effets de cette mesure, puisqu'il se prononce, dans son jugement, sur l'indemnité à allouer à l'avocat d'office, notamment pour la procédure principale, ainsi que, le cas échéant, sur les indemnités au sens de l'<ref-law> que pourraient faire valoir les parties (<ref-ruling> consid. 5.1 p. 201 s.). Cette décision peut ensuite être contestée par la voie de l'appel (<ref-law>), respectivement du recours s'agissant de l'indemnité d'avocat d'office (art. 135 al. 1 et 393 ss CPP; <ref-ruling> consid. 5.2 p. 202). Le recours en matière pénale est ensuite en principe ouvert au Tribunal fédéral contre ces prononcés (<ref-law>).
Partant, faute de préjudice irréparable au sens de l'<ref-law>, le recours est irrecevable.
1.3. Le recourant se prévaut encore d'un déni de justice au sens de l'<ref-law>; il soutient notamment que la cour cantonale aurait, de manière injustifiée, refusé d'appliquer les art. 59 al. 4 et 421 al. 2 let. a CPP.
L'<ref-law> concerne les frais de procédure au sens de l'<ref-law> (arrêts 1B_227/2013 du 15 octobre 2013 consid. 6.2; 1B_51/2013 du 27 septembre 2013 consid. 3.2). Cette question a manifestement été traitée par l'autorité précédente, puisqu'elle les a mis à la charge de l'Etat; elle a en outre statué tant sur ceux relatifs à sa décision annulée par le Tribunal fédéral que sur ceux du prononcé à l'origine de la présente cause (cf. ch. I du dispositif de la décision entreprise). La cour cantonale n'a pas non plus ignoré la possibilité offerte par l'<ref-law>, disposition lui permettant de statuer dans une décision intermédiaire sur les indemnités. Elle a en effet rappelé sa pratique en la matière, à savoir le renvoi de la partie ayant obtenu gain de cause à agir en fin de procédure; tel est notamment le cas si cette dernière ne bénéficie pas d'une défense d'office, situation excluant l'allocation d'une indemnité. Ce choix peut certes ne pas convenir au recourant, mais il n'est pas contraire à la loi vu la nature potestative de la disposition. Il confirme en outre la possibilité de déposer des conclusions en paiement d'une indemnité pour la période alléguée non couverte par la défense d'office (cf. consid. 1.2 ci-dessus).
Partant, dans la mesure où le recours serait recevable en application de l'<ref-law>, le grief de déni de justice devrait être rejeté.
2.
Il s'ensuit que le recours en matière pénale est rejeté dans la mesure de sa recevabilité.
Comme les conclusions du recours étaient dépourvues de chances de succès, l'assistance judiciaire ne peut pas être accordée (<ref-law>). Le recourant, qui succombe, supporte donc les frais judiciaires; vu les circonstances, il se justifie cependant de les réduire (<ref-law>). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours constitutionnel subsidiaire est irrecevable.
2.
Le recours en matière pénale est rejeté dans la mesure de sa recevabilité.
3.
La requête d'assistance judiciaire est rejetée.
4.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
5.
Le présent arrêt est communiqué au mandataire du recourant, au Ministère public central du canton de Vaud et à la Chambre des recours pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 3 juin 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
La Greffière : Kropf