I will suppose $k$ is <b>perfect</b> 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. 

<b>Now we prove the statement</b>. 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$. 

<b>Remark 1</b> By <a href="http://www.math.uconn.edu/~kconrad/math316/316artinschreier.pdf">Artin-Schreier Theorem</a> (that I learnd from D. Harbater), the condition $k$ has <b>finite</b> index in $\bar{k}$ is equivalent to $k$ is algebraically closed or real closed. 

<b>Remark 2</b> 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}}$.