I'll be assuming the question considers time complexity in big-O notation only, because that's common, the simplest, and there is no indication of the contrary. The price to pay for this simplicity is that the resulting time complexity is often a poor way to compare the efficiency of different algorithms.
In this section I restrict to the standard algorithms for addition, multiplication and division (taught in elementary school using base $10$), because they are the simplest, and often used in cryptography (with a higher base like $2^{32}$, but that does not change the time complexity in $O()$ notation).
Computing $A+B$ or $A-B$ in $\mathbb Z$ has time complexity $O(a)$, where $a$ is the number of digits of $A$ (in any base), and $b=O(a)$ using the same convention for $b$. In a cryptographic context, we take the liberty of writing that time complexity $O(\log(A))$.
Computing $A·B$ in $\mathbb Z$ has time complexity $O(a·b)$, or $O(\log(A)·\log(B))$. When $b=O(a)$, that time complexity is $O(a^2)$, or $O(\log(A)^2)$.
Euclidian division of $A\in\mathbb Z$ by $N\in\mathbb{N^*}$, that is computing $R\in[0…N-1]$ and $Q\in\mathbb Z$ such that $A=N·Q+R$, has time complexity identical to that for computing $N·Q$, that is $O(n·q)$, or $O(\log(N)·\log(Q))$.
When performing modular multiplication $A·B\bmod N$ in a cryptographic context, it is typical, and assumed unless otherwise stated, that $a=O(n)$ and $b=O(n)$. It follows that the time complexity of modular multiplication is $O(n^2)$, or $O(\log(N)^2)$.
Modular exponentiation $A^B\bmod N$ with $B>0$ requires at least $\log_2(B)$ modular multiplications (baring shortcuts possible using the factorization of $N$), and less than ${3\over2}·\log_2(B)$ using square-and-multiply. It thus has time complexity $O(n^2·b)$ or $O(\log(N)^2·\log(B))$.
With standard RSA assumptions, computing $C^d \bmod N$ has time complexity $O(\log(N)^3)$; that's because $d$ has size in bits or digits proportional to that of $N$ (and further, close to that), thus the size of $d$ is $O(\log(N))$. This remains unchanged when the CRT technique is used and there is a fixed number of prime factors in $N$ (which reduces the computational cost "only" proportionally to the square of the number of factors).
In RSA, if the public exponent $e$ is fixed, or of bounded size (which is common, and mandated by FIPS 186), then computing $M^e\bmod N$ has time complexity $O(\log(N)^2)$; that's because it is done with a fixed or bounded number of modular multiplications (e.g. $17$ for the common $e=2^{16}+1$). On the other hand, $e$ is sometime allowed to be of the same order of magnitude as $N$ (e.g. in PKCS#1), in which (rare) case $M^e\bmod N$ has time complexity $O(\log(N)^3)$.
$O(\log(N)^3)$ is, of course, not the same as (and more than) $O(\log(N)^2)$. In practice, the RSA private key operation (using $d$) is often much slower than the public key operation (using $e$).
The most commonly taught algorithm to compute the modular inverse $k^{-1}\bmod N$ is the Extended Euclidian algorithm. It is easy to show that it requires at worse $O(\log(N))$ steps, and that the time complexity of any step is $O(\log(N)^2)$ in the worst case (e.g. on the first step for $k\approx\sqrt N$), which is enough for some to give the time complexity as $O(\log(N)^3)$. However, this is grossly pessimistic: the worst case in term of number of steps corresponds to steps of time complexity $O(\log(N))$, and longer steps correspondingly reduce the number of further steps. By induction, I come to the conclusion that the time complexity really is $O(\log(N)^2)$ (but I would not bet the house on that; I welcome a reference, a refutation, or a proof).
Computing $M·k\bmod N$ with the same assumptions as in standard RSA regarding $N$ and $M$, and assuming that $k$ has size proportional to that of $N$, has obviously the same time complexity as modular multiplication, $O(\log(N)^2)$.
Using the same assumptions, computing $C·k^{-1}\bmod N$ has time complexity $O(\log(N)^2)$; that is dominated by the modular inversion step, for any implementation I can think of that uses comparable care in the modular inversion and the modular multiplication.
Notice the importance of the assumption: standard algorithms for multiplication and division. By using the Karatsuba technique for multiplication and Barett reduction for Euclidian division, modular multiplication has time complexity less than $O(\log(N)^{1.585})$ rather than $O(\log(N)^2)$; that's useful, and used in some software implementations of RSA, reducing the time complexity of the private (resp. public) key operation to less than $O(\log(N)^{2.585})$ (resp. $O(\log(N)^{1.585})$). The exponent can go further down using Toom–Cook, which generalizes Karatsuba. Schönhage–Strassen multiplication has time complexity $O(\log(N)·\log\log(N)·\log\log\log(N))$.
Update: the ultimate theoretical technique is $O(\log(N)·\log\log(N)$, by David Harvey and Joris van der Hoeven's Integer multiplication in time $O(n\log n)$, published in Anals of mathematics, March 2021.
The crossover between classical and sub-quadratic algorithms depends a lot on the quality of the implementation, and in particular on how close to the CPU architecture it gets (that's an area where assembly language shines over C, which obstructs access to the carry bit, and often to the whole result of the product of two unsigned integers of the widest size natively supported). While nearly optimal implementations of the classical algorithms using assembly language are relatively common, implementations of sub-quadratic algorithms are often quite sub-optimal, or/and complex (and thus hard to prove right in all corner cases, with the possible exception of Karatsuba).
My usual online references for multiple-precision arithmetic are section 14 in the HAC, and Modern Computer Arithmetic.
modPowis around $O(n^3)$ $\endgroup$