In regards to the typical Cohen or Levi, to what extent is that yichus questionable? If it’s a legitimate safek, should their bechors be required to have a pidyon? Are there other similar halachic repurcussions?
A typical Cohen or Levi who has chazaka in their family that they are kohanim / leviim are trerated as definite kohanim with regards to their Yichus [see Shu’t Minchas Asher 1:80]. Placing a safek on one’s Yichus because of being a Baal Tshuva should be done only with the investigation and desicion of a competent Bais Din which deals in these matters.
If a real safek is established there is a machlokes among the poskim if one is required to do pidyon haben. The question is whether we apply the principle of המוציא מחבירו עליו הראיה, as this is a monetary obligation. This is the opinion of Shulchan Aruch and the Aruch Hashulchan. The Binyan Tzion  and others hold that the overwhelming majority of non Kohanim is enough to demand even a safek kohen performs pidyon. Igros Moshe [Y:D 1:188] rules that one should perform a pidyon, albeit without reciting the bracha.