Causal systems - Paradox? Confusion of definition?
You have your definition of causality wrong. It's actually much simpler and much more intuitive. A causal system is a system in which the output does not depend on future values of the input. This property is not exclusive linear systems and can apply to systems in general. Here are a few examples to illustrate the point:
Causal linear time-invariant system:
$$y[n] = x[n] - 2x[n-1] + 0.5y[n-1]$$
Here $y[n]$ only depends on current and previous values of $x$ and $y$.
Non-causal linear time-invariant system:
$$y[n] = \frac{1}{2}x[n-1] + \frac{1}{2}x[n+1]$$
Also known as a central moving average, this function is non-causal because for output $y[n]$, the $x[n+1]$ term peeks into the future of our input.
Causal non-linear time-invariant system:
$$y[n] = \cos(x[n])$$
This is the example you provided. As you may have guessed by now, since we never look at a future input, this system is causal. In fact, it's even more special than that. Because the current output is a function only of the current input (not past or future inputs) this system is called a memoryless system.
Causal linear time-varying system:
$$y[n] = (n+1)x[n]$$
I made this one up to be somewhat of a brainteaser. At the first glance, it may seem like this system is non-causal because there's this $(n+1)$ term. But this doesn't mater because it's not a time index of $x$. We still only look at the current value of the input and are not peeking ahead. This is also an example of a memoryless system.
A tricky causal non-linear time-varying system:
$$y[n] = e^nx[n] + \ln\left(\left|x[n-1]\right|+1\right) - \pi y[n+1]$$
Clearly, clearly this is a non-causal system because of the $y[n+1]$ term, right? Wrong! This is a classic definition of a recursive causal system with a few terms rearranged. We proceed to bring it into a more standard form in three steps:
$$y[n] = e^nx[n] + \ln\left(\left|x[n-1]\right|+1\right) - \pi y[n+1]$$
$$\pi y[n+1] = e^nx[n] + \ln\left(\left|x[n-1]\right|+1\right) - y[n]$$
$$\pi y[k] = e^nx[k-1] + \ln\left(\left|x[k-2]\right|+1\right) - y[k-1]$$
$$y[k] = \frac{e^nx[k-1] + \ln\left(\left|x[k-2]\right|+1\right) - y[k-1]}{\pi}$$
Second to last line was achieved by substituting $k=n+1$. The trick here is that there is a relationships between outputs at different times. But once you work it out, no output ever depends on future value of an input relative to itself. Non-linearity and time-variance were thrown in to make it more fun and challenging. Make sure you understand what this one says.
As you can see causality can be a property of all sorts of systems and there are many more fun and bizarre examples one can come up with.

Now let's get to resolving your paradox. The key lies in realizing that your definitions of causality and linearity (and perhaps time-invariance, too) a bit entangled and confused. Solving the paradox amusingly is as easy as adding the word linear into both of your definitions (time-invariance will also play a subtle role). Here's how.

Definition 1: A linear system is causal if and only if the output $y[n]$ is a
function of a linear combination of inputs $x[n-k]$ such that $k \ge0$.

This is because not all systems are linear combinations of inputs. Linear systems are. A causal system depends only on past and current inputs, therefore a causal linear system is a linear combination of current and previous inputs. Actually, to be accurate with the definition, linear systems are linear combinations of both inputs and outputs, and in causal linear systems outputs at time $n$ cannot depend on an input at time $m \gt n$.
Also,

Definition 2: A linear time-invariant system is causal if and only if the impulse response
$h[n]=0$ for all $n&lt;0$.

This one is also quite intuitive. All entries of $h[n-k]$ for $k \ge 0$ are the coefficients with which you multiply current and past values of $x$ to get the current output (whether the system is recursive is irrelevant for this case). Notice that this definition only makes sense for linear time-invariant systems! This is because convolution only exists for those. Let's see why linearity is necessary. If you have $h[n+1] \ne 0$, then $x[n+1]$ is contributing to $y[n]$ and that's what makes it non-causal. This is true because in linear systems, if nothing goes in then nothing goes out. This is not generally true for non-linear systems (like in the example you gave), so this definition wouldn't apply.
The system also needs to be time-invariant because it cannot be completely defined by its impulse response unless it's full on LTI. If you run a impulse function $\delta [n]$ through the system
$$y[n] = x[n] + (n+1)x[n+1],$$
you're going to get an output which is an impulse itself (causal... right?). However, the system is clearly non-causal. This is why time-invariance is important. When you run a shifted impulse function $\delta[n-m]$ for $m \ne 0$, its non-causal nature starts manifesting itself.
So, all talking aside, your system is perfectly causal, but your definitions only apply to linear systems, while your system is non-linear. The correct definition of a causal system is that any output $y[n]$ cannot depend on input $x[n+k]$ where $k \gt 0$.