The Shev Shmaitza (1:3) proves from our gemara that safeik d'oraysa must be l'chumra m'doraysa, to the exclusion of the Rambam who holds that m'doraysa one can be meikil and the rabbonon require going l'chumra. The gemara says that the case where safeik bechor can be put into the coral to be counted toward ma'aser b'heima, cannot be speaking about a safeik bechor of a kosher animal. Why? The gemara explains that the torah says יהיה קודש ולא שכבר קדוש, meaning that only things which begin without kedusha can count toward ma'aser b'heima, to the exclusion of a b'chor of a kosher animal which is already kadosh. Now, what makes a safeik b'chor "already kadosh"? Presumably, it is the fact that since it is a safeik, one cannot work with it because safeik d'oraysa l'chumra. From this we see that the torah itself recognizes that fact that a safeik b'chor cannot be worked with and therefore has kedusha status, because safeik d'oraysa is l'chumra on a d'oraysa level. But if safeik d'oraysa was l'kula, then the safeik b'chor would have no kedusha on a d'oryasa level and should not be excluded by the pasuk from ma'aser b'heima.
The steipler (kehilas yakov 8) pushes off the proof of the shmaitza. The question of whether it is forbidden m'doraysa or only d'rabonon to work with a safeik b'chor, does not reflect on the true kedusha status of the b'chor. Although safeik d'oraysa is l'kula, that is just a way that one may conduct themselves in a situation of safeik issur. But, it does not indicate that there is truly no kedusha on the safeik b'chor. Meaning, safeik l'kula is not a method to determine actual status of the animal, it is just a halacha in how to conduct oneself with the safeik b'chor. Therefore, even according to the rambam that safeik is l'kula and the safeik b'chor is permitted to be worked with, the torah still recognizes it as having safeik kedusha and is therefore excluded from the pasuk of יהיה קדש - ולא שכבר קדש. This is a big chiddush in how to look at safeik l'kula and also look at safeik l'chumra - the torah is not being machria that it is considered definite heter or definite issur, rather the torah is merely telling us how to conduct ourselves in a situation of safeik.