When does $\left\Vert f(\mathbf{N}) - f(\mathbf{M})\right\Vert_{\mathrm{op}} \leq k\left\Vert \mathbf{N} - \mathbf{M}\right\Vert_{\mathrm{op}}$ hold?
The term "operator Lipschitz function" is definitely not reserved to the Hilbert-Schmidt norm. On the opposite, I would say that it is mostly used for the operator norm (but not only, see for example https://arxiv.org/abs/0904.4095 ). In particular, the survey that you are citing is using the operator norm.
It is known that not every Lipschitz function is operator Lipschitz (for the operator norm). So the answer to you question 2) is negative. I think that this was a conjecture of Krein, and that the first countexample was produced by Farforovsakaya (1972). A very simple example (Davies and Kato) is given by the absolute value map, which is $1$-Lipschitz but only $\simeq \log(n)$-Lipschitz on $M_n(\mathbf{C})$ (for the operator norm). This is very closely related to the fact that the triangular truncation has norm $\simeq \log(n)$ on $M_n(\mathbf{C})$. In fact, any $1$-Lipschitz function is $O(\log n)$-Lipschitz on $M_n(\mathbf{C})$.
In another direction, sufficient conditions are known to ensure that a function is operator-Lipschitz (for the operator norm), in terms of Besov spaces (Peller, see the survey you cite). It is also known that Lipschitz functions are $O(\max(p,1/(p-1))$-Lipschitz on $S^p$, the Schatten $p$-class. This is the paper I cite above by Potapov and Sukochev.
Note: I am not sure, but I would expect that the fact that Lipschitz functions remain Lipschitz for the Hilbert-Schmidt norm was already known to Krein in the 1960's.
There are several inaccuracies or mistaken impressions in the OP's original question – I say this not to be denigrating, since it is always tricky reading the literature in a different mathematical community from one's own. However it seems worth writing an answer rather than "sniping in comments".
First of all, Aleksandrov and Peller have written many papers on this theme, but in their setting they almost always mean the operator norm not the Frobenius norm. Hence, when you link to their paper https://arxiv.org/abs/1611.01593 you cannot use it to say things about the Kittaneh paper.
Regarding Q1. My impression is that among the infinite-dimensional functional analysis community, "operator Lipschitz" is interpreted with respect to the operator norm. This is for instance what is meant by the Aleksandrov—Peller paper that you linked to, contrary to your impression.
Q2. Note that the equation in A+P that you refer to is for commuting operators only! When two matrices commute and are normal in the technical sense of that word, they can be simultaneously diagonalized (over the complex numbers) and hence estimates of the form you seek can be obtained directly. The difficulty, in both the Kittaneh paper and the series of papers by A+P, lies in the fact that the given matrices might not commute with each other.
Finally, there is an example going back to Kato, and refined in work of Davies I think, which shows that the absolute value function is not "operator Lipschitz". So in full generality the answer to Q2 is no. (I don't have the references to hand but will try to update this later)