This something you could do with a QR update or insert. There is a qrinsert code in MATLAB.
However, you will find that polyfit is pretty fast, and that unless you have thousands of points, that the update will be a waste of time. Note that just doing an update still means you will need to write the code for an updated solution. So you will need to essentially write polyfit anyway.
You would do as well you just write your own simple polyfit code, that does not do the extra computations that polyfit does. The time gained there will be far more significant than what you will gain from the qr update.
The point is, if you don't need the other stuff that polyfit generates and returns, then not computing it will save you time. And a simplified polyfit is trivial to write.
For example, if k is the order polynomial you will fit, and x and y are vectors of the same length...
simplepolyfit = @(x,y,k) bsxfun(@power,x(:),k:-1:0)\y(:);
So it does no error checking. It does not return R^2, or any other parameters of interest.
x = randn(1000,1);
y = rand(1000,1);
The two codes return the same numbers. And the simple version does use a nicely numerically stable routine to compute the solution. If it matters, changing simplepolyfit to return a row vector is a trivial thing to do, so it would be completely consistent with polyfit. This will do it:
simplepolyfit = @(x,y,k) (bsxfun(@power,x(:),k:-1:0)\y(:))';
How about the time for these codes to run?
But on the above simple example, it ran 7 times faster than polyfit, a significant gain in time.
Or you can write a function that will also compute a few minor additional parameters, like residual errors, etc, and still see a gain in time.