We have two integers $i$ and $j$, and the difference between them is large enough such that $(i >j) \rightarrow (K(i) > K(j))$. $K$ is the Kolmogorov complexity function.
We have a set of axioms $\mathcal{A}$ that for sake of argument can prove $i > j$, which is formalized as $\mathcal{A}\vdash i >j$. If we add $(i >j) \rightarrow (K(i) > K(j))$ to $\mathcal{A}$ to make $\mathcal{A}^+$, then $(\mathcal{A} \vdash i > j) \rightarrow (\mathcal{A}^+\vdash K(i) > K(j))$.
By Chaitin's incompleteness theorem, for all finite sets of axioms $S$, there is a value $L_S$ based only on $S$ such that it is impossible to prove $K(b) > L_S$, where $b$ is a bitstring.
Consequently, there is also an $L_{\mathcal{A}^+}$ for $\mathcal{A}^+$. If we set $K(j) > L_{\mathcal{A}^+}$, then for all possible $\mathcal{A}^+$ there is a $j$ such that $\neg(\mathcal{A}^+\vdash K(i) > K(j)$. By modus tollens, this also means that $\neg(A\vdash i >j)$.
This is very strange, because it seems intuitive to me that proving one integer is always larger than smaller integers should always be trivial.
Is there an error in my reasoning?
What you've written is pretty unclear, because the nature of $i$ and $j$ seems to be in flux. But there are basically two possibilities, each of which has a fundamental error.
The most natural interpretation of what you've written is that $i, j$ are chosen at the beginning. The choice of $i$ and $j$ determines $\mathcal{A}^*$ - pick different $i$ and $j$ and you get different systems. So for clarity let's write it "$\mathcal{A}[i,j]$" instead of "$\mathcal{A}^*$" so we can distinguish between systems coming from different $i$ and $j$.
Now the mistake reveals itself. You write "Pick $j$ such that $K(j)>L_{\mathcal{A}^*}$." This looks reasonable because the notation suggests that $\mathcal{A}^*$ is a system defined independently of $j$. But in our notation above, what you've written is $$\mbox{"Pick $j$ such that $K(j)>L_{\mathcal{A}[i, j]}$,"}$$ and now it's clear that the existence of such a $j$ needs to be proved. And, in fact, no such $j$ exists.
In fact, we can add a bit of clarity here. If we pick $i$ and $j$ such that $i>j$, then of course $\mathcal{A}$ proves $i>j$; so the system $\mathcal{A}[i,j]$ is equivalent to $\mathcal{A}\cup\{K(i)>K(j)\}$. And now it's even clearer that we can't in fact find a $j$ which works as desired.
The error above can be resolved if we interpret $\mathcal{A}^*$ as being variables which range over some set of values. One bad interpretation is as $$\mathcal{A}^*_1=\mathcal{A}\cup\{(i>j)\rightarrow (K(i)>K(j)): i,j\in\mathbb{N}\}.$$ This is silly, so let's ignore it.
We actually want $i$ and $j$ to range over reasonable values. This suggests a second interpretation: that we have $$\mathcal{A}^*_2=\mathcal{A}\cup\{(\mbox{$i-j$ is "large enough"})\rightarrow[(i>j)\rightarrow (K(i)>K(j))]: i, j\in\mathbb{N}\}.$$ This is a perfectly reasonable system; indeed, the new sentence is provable in $\mathcal{A}$ itself (as long as $\mathcal{A}$ is reasonably strong)! But this system can't actually prove any new values of $K$, since there will be a limit to the pairs $i, j$ for which $\mathcal{A}^*$ proves the appropriate largeness condition, corresponding to $L_\mathcal{A}=L_{\mathcal{A}^*}$.
Finally, we might consider the system $$\mathcal{A}^*_3=\mathcal{A}\cup\{(i>j)\rightarrow (K(i)>K(j)): \mbox{$i-j$ is "large enough"}\}.$$ This system certainly computes lots of new values of $K$; however, it's not recursively axiomatized! So Chaitin's incompleteness theorem doesn't apply.
So the problem with your argument is an ambiguity around what $\mathcal{A}^*$ is. Once we resolve this ambiguity by picking a precise definition, regardless of how we do this, a clear error emerges - either the nonexistence of the desired $j$, or the weakness/incomputability of the theory.