Dear Rabbi Kornfeld,
The Gemara on 61a says that man was created with two yetsarim, because the word vayitzer is written with two yud'n. Then the Gemara asks, what about animals who we know have a yetzer and yet it does not use the loshon of yetzira there. The posuk later on (when Adam called names) says that Hash-m created (vayitzer) on all the creations. The Gemara's kushya is only that animals have what seems to be a yetzer hara,so why can't we learn it from this posuk?
The Torah indeed says "va'Yitzer" with regard to animals, as the Gemara makes a point of in Nidah 22b. Your question, however, is based on the understanding of the Maharsha, that an animal only has a Yetzer ha'Ra. If so, at most there should be one Yud in its creation.
Anaf Yosef (in the Ein Yakov) answers that the Maharsha is following an opinion he himself expressed elsewhere; in Nidah the Maharsha explains that, according to the Rabanan, the verse you cited is not referring to Behemos. It only mentions Chayah and Of in that verse, and the word Chayah does not include Behemos according to the Rabanan. It is therefore correct to state that the word va'Yitzer never appears in the Torah with reference to a Behemah.
It is also possible to suggest another reading of the Gemara: an animal usually does the will of its creator (by eating grass etc...), which we refer to as Yetzer Tov. The Gemara is suggesting that it even has a Yetzer ha'Ra, and therefore its creation should be noted with two Yuds. The Vayitzer that you found (Bereishis 2:19) only has one Yud, and the Gemara is asking why it does not have two, like the va'Yitzer of man (Bereishis 2:7)