Edit: In the first part, $C^{k,\alpha}$ is understood locally. For a global result, see the final part.
The equation reads $$f(t) = \int_{-\infty}^t e^{-(t - s)\theta} g(s) ds,$$ is equivalent to $$e^{t \theta} f(t) = \int_{-\infty}^t e^{s \theta} g(s) ds,$$ so if $g$ is $C^{k-1,\alpha}$, then $s \mapsto e^{s \theta} g(s)$ is $C^{k-1,\alpha}$, its integral $t \mapsto e^{t \theta} f(t)$ is thus $C^{k,\alpha}$, and finally $f$ is $C^{k,\alpha}$.
Note that this is optimal: if $f$ is $C^{k,\alpha}$, then, by the same argument, $g$ is $C^{k-1,\alpha}$.
Edit: a global result is given below.
The first part shows that if $g \in C^{k-1,\alpha}$ on $[0, 1]$, then $f \in C^{k,\alpha}$ on $[0, 1]$, with $$\|f'\|_{C^{k-1,\alpha}([0,1])} \leqslant C(k,\alpha) \|g\|_{C^{k-1,\alpha}([0,1])}.$$ But the result is clearly translation-invariant, and so
$$\|f'\|_{C^{k-1,\alpha}([a,a+1])} \leqslant C(k,\alpha) \|g\|_{C^{k-1,\alpha}([0,1])} \leqslant C(k,\alpha) \|g\|_{C^{k-1,\alpha}(\mathbb R)}.$$
It follows that
$$\|f'\|_{C^{k-1,\alpha}(\mathbb R)} \leqslant C(k,\alpha) \|g\|_{C^{k-1,\alpha}(\mathbb R)}.$$
It remains to observe that $\|f\|_\infty \leqslant C \|g\|_\infty$, and the desired global estimate follows.
I guess it suffices to give an example for $n = 1$. If $f: \mathbb{R} \to \mathbb{R}$ is an example then $g(x_1, \ldots, x_n) = f(x_1)$ will be an example for any $n \geq 1$.
All we need is a measurable set $A \subseteq \mathbb{R}$ such that both $A$ and its complement have positive measure in every interval. See here, for example. Then define
$$
f(x) = \int_0^x 1_A = \begin{cases}
m(A \cap [0,x])&x \geq 0\cr
-m(A\cap [x,0])&x < 0
\end{cases}.
$$ It should be clear that 1 is a strict Lipschitz constant, but $f'(x) = 1$ at every Lebesgue point of $A$, so the derivative is $1$ on a measure dense set.
Best Answer
Yes. This is true.
Proposition: Let $A\subseteq[0,1]\times\mathbb{R}$ be dense. Then for each $k\geq 0$ and $\epsilon>0$ and $g\in C^k([0,1])$, there is some $C^k$ function $f:[0,1]\rightarrow\mathbb{R}$ where $\{x:(x,f(x))\in A\}$ is dense in $[0,1]$ and where $\|f-g\|<\epsilon$.
Proof: We shall construct a sequence of functions by recursion. Let $f_0=g$. If $f_n$ has already been constructed, then let $U_n=(0,1)\setminus\overline{\{x:(x,f_n(x))\in A\}}$. If $U_n=\emptyset$, then we have already constructed our required function $f$ and we do not need to continue this construction. Otherwise, $U_n$ is a non-empty open set, so $U_n$ is the union of open intervals. Choose the interval $(a_n,b_n)$ in $U_n$ with the maximum length, and then let $f_{n+1}:[0,1]\rightarrow\mathbb{R}$ be a smooth function where $\|f_{n+1}-f_n\|_{C^k}<\epsilon 2^{-(n+1)}$ and where $f_{n+1}-f_n$ is supported on $(a_n,b_n)$ but where $(c,f_{n+1}(c))\in A$ for some $c\in(a_n+(b_n-a_n)/3,a_n+2(b_n-a_n)/3)$. Then $f_n$ is Cauchy, so $f_n\rightarrow f$ for some $f$ in the norm, (and therefore $f_n\rightarrow f$ pointwise as well). We observe that $(U_n)_n$ is a decreasing sequence of open sets with $b_n-a_n\rightarrow 0$. We also observe that $|g-f\|<\epsilon$. Q.E.D.
One can also generalize this question in many ways (such as if we replace $[0,1]$ and $\mathbb{R}$ with differentiable manifolds, complex manifolds, topological spaces and if we require $f$ to be smooth, holomorphic, harmonic, continuous, etc.), and I suspect that in many of those generalized questions the answer is also yes.