How to find out about a particular function or class in which version of Matlab/toolbox it was first introduced? I know I can look through all Release Notes, or Google can help sometime, but is there any better way?
There isn't.
Except, if the place you work at has an active service contract with The MathWorks, you can send a service request and have them do the searching for you (be prepared to argue a bit if they just tell you to google the answer yorself). I do that from time to time in the hope that they'll eventually update the documentation.
Ditto Jonas ... there is no version history for specific functions.
One other thing you can do (if you didn't know this already) is, in your current version of Matlab, to check the value of exist('func'), where func is the name of the MATLAB function. The value this returns for matlab functions is 2, and for built-in functions it's 5.
If you're going for compatibility in your scripts, I would put a condition to check for that function existence before you use it. Otherwise, if you have multiple versions of MATLAB you can run a script to go through all of them or just do it by hand.