I found out my master's thesis topic has already been done (exactly), and my advisor didn't mention this when suggesting it to me - how to proceed?
Note that there is no way anyone knows about your precise situation, except you and your advisor, so I am making some wild guesses on what actually happened.

Perhaps your advisor is hoping to have an efficient implementation of the ideas / algorithms already expressed on the past paper, with the notion that he (or you and him) may later build on your implementation to create something new. In order to create anything new, you have to compare with existing approaches and therefore you still have to implement previous methods. He has given you two options a) Try to expand the ideas of the past paper b) If you cannot do that, just creating a NEW implementation of the original paper is enough for him. This is a MSc thesis and not all MSc theses lead to publishable results. But it still seems like an important project and as such, it seems it could still turn out to be a good MSc thesis and you will have a lot to learn from it.   

So, your main problem is that you think that you cannot expand the original paper to new directions. But if you want to do research this is exactly what you are going to have to do. You should find a topic that interests you ("my supervisor gave a research plan exactly about what i want to do"), study previous literature (which you should have done before choosing the topic) and then expand on previous ideas. Note that since you have worked in industry, you may as well be a better programmer than those 2 PHD students and therefore your implementation might be much more efficient than theirs. This is still a significant contribution which may eventually be published.

My advice: 


Talk to your advisor and state your doubts and clarify the situation.
Implement the paper's ideas as fast and efficient as possible 
Compare your implementation with the paper's results. You should at least aim for a more efficient implementation 
Check related literature that cites this paper. Is this paper, still state-of-the-art? Is this paper cited by anyone? This will show if this project has been picked up by anyone. If it is not, it is reasonable that your advisor wants to build upon the previous paper to further expand it. If someone has extended it or applied it to other use-cases, your assumption that it cannot be improved is wrong and you should think what you can do to further expand it. Either way, you will have an answer about how to proceed. 
Think of any other possible improvements, what else could be done better, in a more efficient way or how this idea could be used in other use-cases.  


Also, you have learnt a valuable lesson. What you want to do in research should correlate with what is already been done. You should study previous research very carefully and exhaustively. If you believe that previous works have already done everything to perfection (which BTW is rarely the case) then you should choose a new topic. Otherwise you are the one that should think what can be improved. I think you pretty much expected that your advisor had a new research idea waiting just for you and all you needed to do was just to implement it. But this was really an unrealistic expectation on your part.