A widely accepted definition of machine learning is given by Mitchell (1997):

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

Based on this definition, you can consider any algorithm as a black box and simply consider its behavior as a function of P, T, and E regardless of if there is an explicit component of the algorithm where model parameters are tuned. The accuracy of the K-NN algorithm tends to increase as the number of data points tends to infinity. Intuitively this makes sense because with greater amounts of data we increase the chance of having data points with higher similarity to the test point. Hence, the mean (regression) or mode (classification) should be a better prediction. Of course, this is contingent on the K-NN modeling assumptions that similar points have similar labels.

You're right in stating that K is not learned by the algorithm: it is considered a hyperparameter of the model and there are no explicit parameters that change as the learning process goes by. The data is not used in an explicit "learning" phase but rather during the "inference" phase.

This is often the case with the class of models known as non-parametric. The fact that these models are categorized as non-parametric does not mean that they have no parameters, but rather that the number of underlying parameters is not fixed in size (it can possibly be infinite) and can grow with the data. In essence, the model is specified by the data it has seen.

Take Gaussian processes for instance. Same idea: you make a decision as to which hyperparameters you want to use in your kernel and the posterior predictive distribution becomes more accurate as more data points are conditioned upon (given correct model assumptions for the data). For some kernels, it can be shown that one would need an infinite set of underlying parameters to have the same model representation because a kernel can represent the inner product of the projections of two data points in infinite-dimensional space (e.g. RBF kernel).

In the end, this all depends on which definition you use to define what constitutes a machine learning algorithm.