Finding maximum subgraph with vertices of degree at most k
Let $G$ be any graph and let $k = 0$.
This problem is, as you correctly pointed out in a comment, better known as Independent Set and is famously NP-complete.
It is therefore unlikely that there is an algorithm solving your problem (which is slightly more general) in polynomial time.