What does temimah mean? A quick rundown of meforshim, and then my own take. We will use a graphic for this. It may pay to click on it to see it larger, in another window.
Let us start with Rashi. We can already see what he is going to say by the way he groups the words. He cites aduma temima and not the word para. Thus, the temimut, completeness, is in the redness. He is basically chanelling a derasha from Sifrei on Chukat, and calling it peshat:
perfectly red Heb. אֲדֻמָּה תְּמִימָה, lit., red, perfect. It shall be perfect in redness, so that two black hairs disqualify it. — [Sifrei Chukath 5]And just because it appears in a midrash does not mean that it is not peshat. Indeed, there is dispute about this, and this struck me as a pasuk it would be useful to check out the Karaites on.
And indeed, if we look at the explanation of Aharon ben Yosef, the Karaite, we see that he endorses Rashi, and the Sifrei's explanation, that temima is modifying the adjective of aduma. This is a parsing issue, so there is no reason why not to accept this as a reading. They reject a separate requirement that the hooves and horns be red, such that if they are black (or in another girsa, white), they are invalid. Because such cannot manifest in reality. The supercommentary connects this to the Mishna in Para, 2:2, פרה שקרניה וטלפיה שחורים, יגוד, which means that they must be cut off and then it is valid.
But regardless, they see temima and modifying aduma. And you can even see this from what they cite, which is the same as Rashi, namely aduma temima.
Ibn Ezra parses it slightly differently. You can see this from the fact that he cites the full phrase para aduma temima. He says that this means that the female cow is not a ketana, but is rather fully mature. I think he is parsing it such that temima modifies para.
One could argue it in all sorts of ways, but I think the trup supports Ibn Ezra more than Rashi here. (Click to see the picture.) The trup, as you can see above, on para aduma temima is kadma veazla revii. The kadma is a conjunctive trup, while the azla and revii are disjunctive. Effectively, this groups para aduma together on one branch, and temima on the other branch, such that temima would be modifying the entire entity, which is the red cow, which is in other words the cow. If it were complete in redness, wouldn't we expect to see aduma temima grouped together? It is possible I am missing something, but I would guess so.
Of course, if my trup chart above is correct, it is not modifying just para aduma but rather entire phrase of vayikchu eilecha fara aduma. It seems in this way to stand alone, away from all that. This makes me less likely to endorse temima as going on aduma. I think it modifying the full cow is still possible, but there is yet another possibility.
Who says that a peshat must accord with the trup, though. The trup is just another perush, and while biblical commentators try to remain true to the trup, they on occassion feel free to diverge.
Sifsei Chachamim (above) gives a reason for Rashi's peshat. He notes that the pasuk continues with אֲשֶׁר אֵין-בָּהּ מוּם. Why would the pasuk repeat itself to no valid purpose. Therefore, rather than taking temima as an adjective in and of itself ("faultless/unblemished"), it modifies the adjective "red".
So here we have a tempting alternative. Temima means "faultless." And in some pashtanim, Tanach does repeat itself. It is called kefel lashon.
This is indeed what Shadal writes:
תמימה אשר אין בה מום: כפל לשון, כמו ( ויקרא כ"ב כ"א) תמים יהיה לרצון כל מום לא יהיה בו
You can see even by his dibbur hamatchil his explanation. He connects temima to asher ain bah mum. Thus, it means faultless. He cites Vayikra 22:21 as an example.
tamim is defined as lacking a mum.
I would offer an expansion upon this idea. Namely, they are not synonyms. Rather, the cow must be temima. The portion of the pasuk after the etnachta is the definition.
Thus, temima means entirely pure and dedicated. How so?
1) אֲשֶׁר אֵין-בָּהּ מוּם -- thus physically whole and perfect
2) אֲשֶׁר לֹא-עָלָה עָלֶיהָ עֹל -- and never dedicated to another purpose, so untouched in this way.
Thus, it is not just kefel lashon, but a general description of the requirement of temima followed by two elaborations to make clear just what temima means.