I found this question here on MO: What about the fastest-growing non-computable function ? and at first I thought I misread it. Given that all uncomputable functions seem to grow mind-bogglingly fast, the natural question to me seems how slow they can still be, not how fast.
Then again I am not sure if this question can have a well defined answer. But any insight is welcome!
Here's one possible interpretation of your question, I don't know if this is what you're after:
Proposition. For every nondecreasing $b\colon\mathbb{N}\to\mathbb{N}$ such that $b(n) \to +\infty$ as $n \to +\infty$ there exists a nondecreasing $f\colon\mathbb{N}\to\mathbb{N}$ which is uncomputable and such that $f(n) = O(b(n))$ as $n \to +\infty$. (Of course, one must have $f(n) \to +\infty$ as $n \to +\infty$ as any bounded nondecreasing function on the integers is eventually constant, hence computable.)
Thus, uncomputable functions can grow arbitrarily slowly, even if we restrict ourselves to nondecreasing functions so as to make “growth rate” meaningful.
Proof. Let $0=n_0<n_1<n_2<\cdots$ be the integers such that $b(n)>b(n-1)$ (since $b$ tends to $+\infty$, there must be infinitely many such integers). For $n_i\leq m < n_{i+1}$ (so that $b(m) = b(n_i)$), define $f(m) := 2b(m) + h(i)$ where $h(i)$ is $1$ or $0$ according as the $i$-th Turing machine halts or not. Clearly, $f(n) = O(b(n))$ as $n\to+\infty$, and $f$ is nondecreasing. Given an oracle that computes $f$, we can compute $b$, hence also $i\mapsto n_i$, hence $h$. So $f$ cannot be computable. ∎
