K Perfect Subgraph Algorithm
This problem is NP-hard, meaning it's very unlikely that any algorithm exists that can solve every instance in polynomial (let alone linear!) time.  I'll show this by reducing the NP-hard problem Clique to this problem.  In Clique, we are given an undirected graph $F$ and a number $K$, and the task is to determine whether or not $F$ contains a clique (complete subgraph) with at least $K$ vertices.  The strategy will be to add universal vertices to $F$ -- that is, new vertices that are connected to all existing vertices -- and show that doing so grows the size of cliques in $F$, but does not grow the size of any other regular subgraphs in $F$.

Let there be $n$ vertices in $F$.  We will construct an instance $(G, k)$ of your problem from the given instance $(F, K)$ of the Clique problem:


$G$ is formed by adding $n+1$ new vertices to $F$ that are adjacent to each other and to every vertex in $F$.
$k = K + n$.


First we show that if there is a clique in $F$ of size at least $K$, then there is a regular subgraph with degree at least $K+n$ in $G$.  Clearly a clique of $K+n+1$ vertices can be formed by including the $K$ clique vertices in $F$ and all $n+1$ new vertices.  A clique containing $i$ vertices is regular with degree $i-1$, so this clique is regular of degree at least $K+n$.  Thus a YES answer to the given Clique problem implies a YES answer to the constructed instance of your problem.

Now we show that if there is a regular subgraph $H$ with degree at least $K+n$ in $G$, then there is a clique of size at least $K$ in $F$.  First observe that this $H$ must include at least one of the $n+1$ newly added universal vertices, since the largest degree obtainable using just the original $n$ vertices of $F$ is $n-1 &lt; n+K$.  The following lemma is key:


  Lemma: If a regular graph $I$ contains a universal vertex, then it must be a clique.
  
  Proof: Let $c \ge 1$ be the number of universal vertices in $I$, and let $a$ be the number of other vertices.  Since $I$ is regular, it
  must be that every non-universal vertex has the same degree $c+d$ for
  some $d$ -- that is, removing the $c$ universal vertices from $I$ must
  leave a $d$-regular subgraph, which I'll call $I'$.  Again, since $I$
  is regular, we must have that the degree $c-1+a$ of each universal
  vertex in $I$ is equal to the degree $c+d$ of the other vertices.  But
  this implies $a-1=d$, i.e., $I'$ is a clique of $a$ vertices, and thus
  $I$ is a clique of $c+a$ vertices.


Since $H$ contains at least one universal vertex, by the above lemma, it must be a clique of size at least $K+n+1$.  Since we only added $n+1$ universal vertices to $G$, at least $K$ of the vertices in $H$ must have come from the original graph $F$, where they also form a clique since every induced subgraph of a clique is a clique.  Thus a YES answer to the constructed instance of your problem implies a YES answer to the given Clique problem.

Since a YES answer to one problem instance implies a YES answer to the other, it follows that a NO answer to one problem instance also implies a NO answer to the other.  Thus any algorithm that could solve your problem could also solve Clique.  Since constructing the instance of your problem requires only polynomial time, a polynomial-time algorithm that could solve your problem could also solve Clique in polynomial time.