The gemara says that if one was bringing a korban mincha in Yerushalayim they make shehechiyanu. Rashi explains that we are speaking about a koehin who has never before brought a korban mincha or at least never brought this type of korban mincha. According to Rashi the gemara is being mechadesh that one make a bracha of shehechiyanu on their first time fulfilling a mitzvah. Tosafos says that the reason for making the shehechiyanu is not because it is his first time but because the kohanim were divided into mishmaros and batei avos so that each kohein would only do avoda twice a year. Tosafos holds that bringing korbanos is considered a mitzvah that comes m'zman l'zman and is worthy of shehechiyanu.
There is a discussion in the Rishonim whether one makes a bracha on the mitzvah of kisuy ha'dam (covering the blood when schechting a bird or chaya). According to Tosafos this gemara would not be a source for the bracha on kisuy ha'dam because you would only make shehechiyanu on mitzvos that are somewhat dependent on the calendar and therefore come m'zman l'zman. However, according to Rashi this gemara would set a precedent for making a shehechiyanu the first time that one fulfills a mitzvah. The Shach (y.d. 28:2) quotes the rokeach who says based on this gemara that the first time in one's life that they fulfill any mitzvah, they make shehechiyanu. The shach points out that our minhag is not to make a shehechiyanu the first time we fulfill a mitzvah from the fact that we don't make shehechiyanu on tzitzis and tefillin. He therefore argues on the Rama who says to make shehechiyanu the first time doing kisuy ha'dam. The tzvi la'tzadik justifies the position of the Rama. The Rama holds like Rashi/Rokeach that we make a bracha the first time performing a mitzvah, so long as it is fulfilled the first time as an adult. Therefore, tzitzis and tefillin which people usually begin before bar mitzvah, they don't make a shehechiyanu when they are pre-bar mitzvah, but also don't make it upon becoming bar mitzvah since they have already done the mitzvah before. The Gilyon MaHarsha (gemara) asks from kiddushin and mezuza (which are performed the first time as an adult) and still we don't make shehchiyanu. The Pri Megadim holds that since it is a safeik (according to Tosafos we don't have a source for making a shehchiyanu the first time performing a mitzvah), one shouldn't make shehechiyanu the first time performing a mitzvah.