Shirk is calling someone God, assigning divinity to someone other than God, or assigning the offices of divinity to someone other than God.
Saying "'Ali is the wali of God" is not shirk, because it is not doing any of the above.
Furthermore, the Qur'an speaks of the "awliya' Allah" (plural of wali) with respect to human beings. Therefore, it is not shirk to say that Imam 'Ali is the wali of Allah, since Allah uses that phrase Himself. Given his high level of spirituality and service to Islam, very few Muslims would disagree with the idea behind saying "'Ali is the wali of Allah," although this phrase has become associated with Shi'ism.
Therefore, the biggest objection that someone could put forward to saying this in the adhan is that it does not belong in the adhan, not that it is shirk or an untrue statement.
It is not necessary to say "'Ali is the wali of Allah" in the adhan or kalimah. It is optional to say that. Shi'is generally do not consider it part of the adhan or salat. If it is said in the adhan, it is said as an optional thing which is said for blessings, or because it is seen as recommended, not as an actual part of the adhan. This is similar to how one might recite salawat after the Prophet's name during the adhan - it is done as an optional thing and not out of the belief that it is a formal part of the adhan.
For matters of religious law, such as the salat or converting to Islam, it is enough to say "there is no God but Allah and Muhammad is his Prophet".
However, due to the Shi'i belief in the Imamate, some Shi'is might feel it is a more complete or comprehensive statement of faith to also say "'Ali is the wali of Allah" (because the 3 statements cover monotheism, prophethood, and imamate); one might also say it to indicate a desire to convert specifically to Shi'ism. But it is not necessary.
Among Shi'is, it has become common to say "'Ali is the wali of Allah" during the adhan. There are some narrations indicating that this was said in the presence of the Prophet, for instance, that on the Day of Ghadir Salman al-Farsi recited it during the adhan, and the Prophet approved of it.
Similarly, regarding the kalimah, there are narrations in Sunni and Shi'i books connecting endorsement of Imam 'Ali to endorsement of Allah and the Prophet. For instance, it is said that it is written on the Throne of God: "There is no God but Allah, Muhammad is My servant and messenger, and 'Ali was his supporter."
Sadly, today, some Muslims attack each other over very small details of practice. They dislike some things because they are different from the Islam they are familiar with, or because they are symbolic of a different sect. It would be better to move towards a spirit of tolerance and acknolwedge that there are multiple ways in which Islam is lived today. After all, even if two people are reciting the adhan differently, they are still reciting the adhan. There are many people who don't care about God at all. Why not focus on the big things such as discussing the existence and relevance of God, rather than focusing on small details and trying to "prove" who is right?
(This is not directed at you personally since I am sure it is a genuine question, and it is a good question to ask and know about, but rather it is an overall comment regarding the situation of the Muslim world today and the types of arguments that are had over how to do wudhu and so forth.)