Sorry if this is too elementary, I just wanted to make this answer as self-contained as possible. In fact, you can't do what you're describing: the best polynomial of degree $k+1$ will always fit at least as well as the best polynomial of degree $k$, since the set of $k+1$ degree polynomials includes all $k$ degree polynomials (just set $a_{k+1} = 0$). As you continue to increase $k$, at a certain point you will be able to find a polynomial that fits the data perfectly (i.e. with zero error).
This usually isn't a very attractive solution because it's hard to imagine a process that ought to be described by e.g. a million-degree polynomial, and it's almost certain that this kind of model will be more complex than is necessary to adequately describe the data. This phenomenon is called overfitting, and a good example is this Wikipedia image. The data is clearly close to linear, but it's possible (but not desirable) to get a lower error with a more complex model.
In general, the goal is to minimize the error that would occur on new data from the same underlying model, rather than on the current set of data. Often it isn't possible or practical to just get more data, so usually one would employ some form of cross-validation to find the model that generalizes the best to unseen data. There are lots of forms of cross-validation, and you can read about them in the Wikipedia article or in numerous answers on CrossValidated (ha!). But in effect they all can be reduced to: fit a model on some of your data and use this to predict the values for the remainder of your data. Do this repeatedly and choose the model (in this case, the degree of polynomial) that gives you the best performance on average.
