The paradox can be resolved by being clear about how we want to define time-reversal. In the simplest case of a non-interacting, single-component complex scalar field, a typical definition takes time-reversal to be the antilinear transformation that replaces the field operator $\phi(t,x)$ with $\phi(-t,x)$. This is consistent with the calculation shown in the question. There is no contradiction, because antilinearity doesn't imply that the result should be $\sim\phi^*$.
Whether or not a given transformation is a symmetry of the given model is a separate question, not addressed here; that would require specifying the whole model. The key message here is simply that if we're clear with definitions, then no contradictions arise.
Quantum (field) theory is formulated using operators on a Hilbert space. For the question being asked here, the Hilbert space is not important, so we can think of the operators as elements of an abstract algebra (a C*-algebra) instead of as operators on a Hilbert space, but to be concise, I'll still call them "operators."
Every operator $A$ has an adjoint, often denoted $A^\dagger$ by physicists and often denoted $A^*$ by mathematicians. I'll use the notation $A^\dagger$ here. The adjoint satisfies
for all complex numbers $z$, where $z^*$ denotes the complex conjugate. It also satisfies
We can think of the adjoint as an extension of complex conjugation from complex numbers to operators.
An antilinear transformation takes each operator $A$ and returns a new operator, which I'll denote $\sigma(A)$, subject to these rules:
Notice that (4) preserves the order of multiplication but (2) reverses it.
The quantum "complex" scalar field is a collection of operators $\phi(t,x)$, one per point in spacetime. (We can make this well-defined by treating spacetime as a very fine discrete lattice, but that level of detail won't be needed here.) Saying that the field operator is "complex" is a common but dangerous way of saying that it is not self-adjoint: $\phi^\dagger(t,x)\neq\phi(t,x)$. The field operator $\phi(t,x)$ is an operator, not a complex number.
With all of that in mind, suppose that we define time-reversal to be the antilinear transformation $\sigma_T$ whose effect on the field operator is
For any other operator $A$ that can be expressed in terms of $\phi(t,x)$, such as the operators $a_k$ or $b_k$ used in the question, the effect of $\sigma_T$ on $A$ can be derived from this definition. In particular, the requirement that $\sigma_T$ be antilinear implies
for all complex numbers $z$. This definition of time-reversal is consistent with the calculation shown in the question. The key message here is that antilinearity does not imply that the result must be $\sim\phi^*$.
The structure of a given model might also motivate defining charge conjugation to be an ordinary linear transformation $\sigma_C$ that satisfies
(This is typically done in scalar QED, for example.) The requirement that $\sigma_C$ be linear implies
for all complex numbers $z$. Although this charge conjugation transformation takes the adjoint of the field operator, it does not take the adjoint of most other operators. It is a linear transformation, which preserves the order of multiplication as shown in (9), in contrast to (2).
The transformations $\sigma_T$ and $\sigma_C$ were defined above by specifying two things:
Their effect on all other operators may be deduced from these, assuming that all other operators may be expressed in terms of the field operators (as usual in QFT). More general definitions of such transformations can allow them to mix different components or different fields with each other; only simple representative possibilities were considered here.
P.S. - An antilinear transformation $\sigma_T$ can be written as
for an antilinear operator $T$. This can be a useful way to write it when working with vectors in the Hilbert space, but this fact does not affect the answer to the question.