First, if $k(n)$ and $T(n)$ are non-negative functions satisfying $$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$ for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite limit, and in particular, it cannot be decreasing. But if $T(n_0+1)\ge T(n_0)$, then $T(n+1)>T(n)$ for all $n>n_0$ by induction on $n$. Thus, $T$ is eventually increasing.

Second, proving bounds on $T(n)$ is inconvenienced by the presence of a negative term in $(*)$. We can fix this by defining a new function $$S(n)=\begin{cases}T(\tfrac n2)&\text{$n$ even,}\\T(\tfrac{n+1}2)-T(\tfrac{n-1}2)&\text{$n$ odd,}\end{cases}$$ which (as we just proved) is also eventually nonnegative, and satisfies the recurrence $$S(n)=\begin{cases}S(n-1)+S(n-2)&\text{$n$ even,}\\ S(n-1)+S(n-2)+S(n-k'(n))+3^{(k'(n)-1)/2}&\text{$n$ odd,}\end{cases}\tag{${*}{*}$}$$ where $k'(n)=2k((n-1)/2)+1$.

This makes it obvious that $$S(n)\ge S(n-1)+S(n-2),\qquad n\gg0,$$ hence $$S(n)=\Omega(\phi^n)\quad\text{and}\quad T(n)=\Omega(\phi^{2n}),$$ where $\phi=(1+\sqrt5)/2\approx1{.}618$ is the golden ratio.

I claim that a suitable choice of $k(n)$ gives a matching upper bound. The right choice is to make the two terms involving $k'$ approximately equal; since we are shooting for $S(n)\approx\phi^n$, this means $$\phi^{n-k'(n)}\approx3^{k'(n)/2},$$ thus $$k'(n)\sim\beta n,\qquad\beta=\frac{2\log\phi}{2\log\phi+\log3}\approx0{.}467$$ and $k(n)\sim\beta n$ as well. So, let us assume $$\beta n+c\le k'(n)\le\beta n+d$$ for some constants $c,d$ (with some conditions on $c$ below). I claim that with this setting, any nonnegative solution of $({*}{*})$ satisfies $$S(n)\le a\phi^n-b\psi^n\tag{${*}{*}{*}$}$$ for some constants $a,b>0$, where $$\psi=3^{\beta/2}=\phi^{1-\beta}\approx1{.}29,$$ and consequently $$T(n)=O(\phi^{2n}).$$

Pick $n_0>2$, $a,b>0$ such that $({*}{*})$ holds for $n\ge n_0$, and $({*}{*}{*})$ holds for $n\le n_0$ (there will be one more condition below). We want to show $({*}{*}{*})$ for all $n$ by induction. The induction step goes as follows: $$\begin{align*} S(n)&\le a(\phi^{n-1}+\phi^{n-2})-b(\psi^{n-1}+\psi^{n-2})+a\phi^{(1-\beta)n-c}+3^{(\beta n+d)/2}\\ &=a\phi^n-b(\psi^{-2}+\psi^{-1})\psi^n+(a\phi^{-c}+3^{d/2})\psi^n\\ &\le a\phi^n-b\psi^n. \end{align*}$$ The last step is valid if $$b(\psi^{-2}+\psi^{-1}-1)\ge a\phi^{-c}+3^{d/2}.\tag{${*}{*}{*}{*}$}$$ We can arrange this condition by observing that the other requirements on $a,b$ continue to hold if we increase both by the same amount; this will eventually make $({*}{*}{*}{*})$ true if $c$ is sufficiently large so that $$\psi^{-2}+\psi^{-1}-1>\phi^{-c}.$$

First, if $k(n)$ and $T(n)$ are non-negative functions satisfying $$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$ for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite limit, and in particular, it cannot be decreasing. But if $T(n_0+1)\ge T(n_0)$, then $T(n+1)>T(n)$ for all $n>n_0$ by induction on $n$. Thus, $T$ is eventually increasing.

Second, proving bounds on $T(n)$ is inconvenienced by the presence of a negative term in $(*)$. We can fix this by defining a new function $$S(n)=\begin{cases}T(\tfrac n2)&\text{$n$ even,}\\T(\tfrac{n+1}2)-T(\tfrac{n-1}2)&\text{$n$ odd,}\end{cases}$$ which (as we just proved) is also eventually nonnegative, and satisfies the recurrence $$S(n)=\begin{cases}S(n-1)+S(n-2)&\text{$n$ even,}\\ S(n-1)+S(n-2)+S(n-k'(n))+3^{(k'(n)+1)/2}&\text{$n$ odd,}\end{cases}\tag{${*}{*}$}$$ where $k'(n)=2k((n+1)/2)-1$.

This makes it obvious that $$S(n)\ge S(n-1)+S(n-2),\qquad n\gg0,$$ hence $$S(n)=\Omega(\phi^n)\quad\text{and}\quad T(n)=\Omega(\phi^{2n}),$$ where $\phi=(1+\sqrt5)/2\approx1{.}618$ is the golden ratio.

I claim that a suitable choice of $k(n)$ gives a matching upper bound. The right choice is to make the two terms involving $k'$ approximately equal; since we are shooting for $S(n)\approx\phi^n$, this means $$\phi^{n-k'(n)}\approx3^{k'(n)/2},$$ thus $$k'(n)\sim\beta n,\qquad\beta=\frac{2\log\phi}{2\log\phi+\log3}\approx0{.}467$$ and $k(n)\sim\beta n$ as well. So, let us assume $$\beta n+c\le k'(n)\le\beta n+d$$ for some constants $c,d$ (with some conditions on $c$ below). I claim that with this setting, any nonnegative solution of $({*}{*})$ satisfies $$S(n)\le a\phi^n-b\psi^n\tag{${*}{*}{*}$}$$ for some constants $a,b>0$, where $$\psi=3^{\beta/2}=\phi^{1-\beta}\approx1{.}29,$$ and consequently $$T(n)=O(\phi^{2n}).$$

Pick $n_0>2$, $a,b>0$ such that $({*}{*})$ holds for $n\ge n_0$, and $({*}{*}{*})$ holds for $n\le n_0$ (there will be one more condition below). We want to show $({*}{*}{*})$ for all $n$ by induction. The induction step goes as follows: $$\begin{align*} S(n)&\le a(\phi^{n-1}+\phi^{n-2})-b(\psi^{n-1}+\psi^{n-2})+a\phi^{(1-\beta)n-c}+3^{(\beta n+d+1)/2}\\ &=a\phi^n-b(\psi^{-2}+\psi^{-1})\psi^n+(a\phi^{-c}+3^{(d+1)/2})\psi^n\\ &\le a\phi^n-b\psi^n. \end{align*}$$ The last step is valid if $$b(\psi^{-2}+\psi^{-1}-1)\ge a\phi^{-c}+3^{(d+1)/2}.\tag{${*}{*}{*}{*}$}$$ We can arrange this condition by observing that the other requirements on $a,b$ continue to hold if we increase both by the same amount; this will eventually make $({*}{*}{*}{*})$ true if $c$ is sufficiently large so that $$\psi^{-2}+\psi^{-1}-1>\phi^{-c}.$$