@Satya, the Prophet Muhammad (SAWS) has been mentioned in earlier scriptures including the Hindu Vedas where he is directly referred to by his name, viz., "Ahmed." And he is also mentioned in the biblical testaments, both old and new. Links to this have been provided above by other members who have also replied to this question. (Check @Tabrez Ahmed's reply above.)
Insofar as other prophets go, yes, each prophet who came before Muhammad (SAWS) came for a specific community or time. But Muhammad (SAWS) came for the whole of humanity. So the question you ask is very valid and begs to be answered: "Given that message of prophets are subject to change with time, can I assume that message of Prophet Muhammad may change?"
To this question I would ask you to look at history from 10,000 feet up. Earlier prophets came and went and you will still find mention of some of them in local scriptures of various religions. (However, as Muslims, we look to the Qur'an and the sayings of the Messenger (SAWS) for claiming with any level of surety that such-and-such was a prophet.) When these earlier prophets came, the whole of humanity was fragmented with each living in a separate section of the world and unaware of other civilizations that existed at their time. So, we can surmise that there may have been more than one prophet at one time in diametrically opposite sides of the world who were even unaware of each other or indeed if any civilization existed beyond the community where they were present.
However, the timing at which Muhammad (SAWS) was sent is key to understanding his finality. He came at the eve of the integration of the world, such that today, just 1400 years later which is like a blink of an eye in terms of history, we can communicate with each other in a fraction of a second. Within just a few centuries of his arrival, the Americas were inhabited by the "known world," as we refer to our own civilization that existed then. Today, there is not a single country in the world that does not have Muslims in it who would gladly share information about Islam with their neighbors.
Taking this timing into consideration, one can rightly arrive at the conclusion that prophet Muhammad (SAWS) came at a time when the entire world was starting to become a global village. To that end, the shareeah (or the specific set of laws) that were brought by the last messenger are applicable to every single human alive today.
Another interesting fact that most folks (including many Muslims) are unaware of is that the moment Muhammad (SAWS) made public his mission of being the messenger of God, all the other shareeahs automatically became obsoleted and all the people of the world since that time till the last day, regardless of their religious affiliations, will be considered on the day of Qiyamah (Judgement Day) to be his nation, regardless of whether they believe in him or not, and regardless of whether they keep following the old and outdated shareeahs of earlier prophets.
About Islam being the perfect religion, you may be referring to the verse of the Qur'an (5:3) "This day I have perfected your religion for you ..." We have to know the context in which it was revealed to understand what perfection it is referring to. The perfection mentioned here refers to the shareeah of Muhammad (SAWS) becoming perfect and complete for this nation of Muhammad (SAWS). It is interesting to note that when Umar, a very close and well-known companion of the Prophet (SAWS) heard this he cried... when asked about this, he replied that since the religion is perfect today, from now on it can only deteriorate,’ which essentially means that its adherents can only decrease in following it, but when it was being revealed, the early Muslims keenly followed every injunction and were ever-willing to fulfill it to the best possible extent.
Your last question about the kalimah, or the declaration of faith, "There is no god except Allah, and Muhammad (SAWS) is His Prophet," every single prophet before Muhammad (SAWS) came with the same principle, that is, there is no god except Allah. (You will find the same in the Hindu Vedas too.) Only the messenger was different for different times.
HTH.
