I will suppose $k$ is perfect for simplicity.
Let $k_B$ be the residue field of $B$. Then there
Statement: There exists $B$ with $k_B$ algebraic over residue extension $k$ k_B/k$if and only if$k$has infinite index in its algebraic closure. And this implies that$[k_B : k]=+\infty$. First we prove the following facts: (1) Let$F/K$be an extension of discrete valuation fields. If the residue extension$k_F/k$is finite, then$F/K$is finite. (2) Let$K^{sh}$be a strict henselization of$K$. If$k$has infinite index in its algebraic closure, then there exists$\theta\in\widehat{K^{sh}}$(completion) which is transcendental over$K$. Proof of (1). Let$k_F$be the residue field of$F$. Lift a basis of$k_F/k$to$a_1,...,a_r\in O_F$(valuation ring of$F$). Let$e$be the ramification index of$O_F$over$R$and let$\pi_F$be a uniformizing element of$O_F$. Then the finite set $${\lbrace a_i \pi_F^{j} \rbrace}_{1\le i\le r, \ 0 \le j \le e-1}$$ generates a submodule$M$of$O_F$such that$O_F=M+\pi^n O_F$for all$n\ge 1$and one can check that$M\cap \pi^n O_F = \pi^n M$. As$M$is automatically complete for the$\pi$-adic topology (it is finitely generated), this implies that$O_F=M$, thus$F/K$is finite. Proof of (2). For any$n\ge 1$, there exists a subextension of$\bar{k}$of degree at least$n$. By primitive element theorem, there exists$x_n\in \bar{k}$of degree at least$n$over$k$. Lift$x_n$to a$\theta_n\in K^{sh}$with$[K(\theta_n):K]=[k(x_n):k]$(we use the fact that$K$is henselian here). Set $$\theta= \sum_{n\ge 1} \theta_n \pi^{n-1} \in \widehat{K^{sh}}.$$ We are going to show that$\theta$is transcendental over$K$. Suppose the contrary. Then$\theta\in K^{sh}$. Let$L=K[\theta] \subseteq K^{sh}$. As$\theta = \theta_1 \mod \pi$and$L$is henselian, we have$\theta_1 \in L$. Similarly,$(\theta-\theta_1)/\pi \in L$is equal to$\theta_2 \mod \pi$, hence$\theta_2 \in L$and so on. Therefore$\theta_n\in L$for all$n$. Hence$[L : K] \ge n$for all$n$. Contradiction. Now we prove the statement. If$k_B$is algebraic over$k$, then$k_B/k$is infinite by (1). In particular,$k$has infinite index in its algebraic closure. Conversely, suppose$k$satisfies this property. Let$\theta\in \widehat{K^{sh}}$given by (2). Consider the field$K(\theta)\subseteq \widehat{K^{sh}}$. It is isomorphic to$K(t)$. We endow it with the discrete valuation induced by that of$\widehat{K^{sh}}$. This valuation extends that of$K$. So its valuation ring$B$dominates$R$and$k_B$is contained in$\bar{k}$, hence algebraic over$k$. Remark 1 By Artin-Schreier Theorem (that I learnd from D. Harbater), the condition$k$has finite index in$\bar{k}$is equivalent to$k$is algebraically closed or real closed. Remark 2 If$k$is not necessarily perfect, (1) is still true (same proof). Suppose$k$has infinite index in its algebraic closure, then the existence of$B$with$k_B$algebraic over$k$is still true, but we have to work with (finite extension of)$W(\bar{k})$or$\bar{k}((t))$instead of$\widehat{K^{sh}}$. 1 I will suppose$k$is perfect for simplicity. Let$k_B$be the residue field of$B$. Then there exists$B$with$k_B$algebraic over$k$if and only if$k$has infinite index in its algebraic closure. And this implies that$[k_B : k]=+\infty$. First we prove the following facts: (1) Let$F/K$be an extension of discrete valuation fields. If the residue extension$k_F/k$is finite, then$F/K$is finite. (2) Let$K^{sh}$be a strict henselization of$K$. If$k$has infinite index in its algebraic closure, then there exists$\theta\in\widehat{K^{sh}}$(completion) which is transcendental over$K$. Proof of (1). Let$k_F$be the residue field of$F$. Lift a basis of$k_F/k$to$a_1,...,a_r\in O_F$(valuation ring of$F$). Let$e$be the ramification index of$O_F$over$R$and let$\pi_F$be a uniformizing element of$O_F$. Then the finite set $${\lbrace a_i \pi_F^{j} \rbrace}_{1\le i\le r, \ 0 \le j \le e-1}$$ generates a submodule$M$of$O_F$such that$O_F=M+\pi^n O_F$for all$n\ge 1$and one can check that$M\cap \pi^n O_F = \pi^n M$. As$M$is automatically complete for the$\pi$-adic topology (it is finitely generated), this implies that$O_F=M$, thus$F/K$is finite. Proof of (2). For any$n\ge 1$, there exists a subextension of$\bar{k}$of degree at least$n$. By primitive element theorem, there exists$x_n\in \bar{k}$of degree at least$n$over$k$. Lift$x_n$to a$\theta_n\in K^{sh}$with$[K(\theta_n):K]=[k(x_n):k]$(we use the fact that$K$is henselian here). Set $$\theta= \sum_{n\ge 1} \theta_n \pi^{n-1} \in \widehat{K^{sh}}.$$ We are going to show that$\theta$is transcendental over$K$. Suppose the contrary. Then$\theta\in K^{sh}$. Let$L=K[\theta] \subseteq K^{sh}$. As$\theta = \theta_1 \mod \pi$and$L$is henselian, we have$\theta_1 \in L$. Similarly,$(\theta-\theta_1)/\pi \in L$is equal to$\theta_2 \mod \pi$, hence$\theta_2 \in L$and so on. Therefore$\theta_n\in L$for all$n$. Hence$[L : K] \ge n$for all$n$. Contradiction. Now we prove the statement. If$k_B$is algebraic over$k$, then$k_B/k$is infinite by (1). In particular,$k$has infinite index in its algebraic closure. Conversely, suppose$k$satisfies this property. Let$\theta\in \widehat{K^{sh}}$given by (2). Consider the field$K(\theta)\subseteq \widehat{K^{sh}}$. It is isomorphic to$K(t)$. We endow it with the discrete valuation induced by that of$\widehat{K^{sh}}$. This valuation extends that of$K$. So its valuation ring$B$dominates$R$and$k_B$is contained in$\bar{k}$, hence algebraic over$k$. Remark 1 By Artin-Schreier Theorem (that I learnd from D. Harbater), the condition$k$has finite index in$\bar{k}$is equivalent to$k$is algebraically closed or real closed. Remark 2 If$k$is not necessarily perfect, (1) is still true (same proof). Suppose$k$has infinite index in its algebraic closure, then the existence of$B$with$k_B$algebraic over$k$is still true, but we have to work with$W(\bar{k})$or$\bar{k}((t))$instead of$\widehat{K^{sh}}\$.