According to Wikipedia, the $k$-core of a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$.
Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until either $S_k=\emptyset$ or there are no such vertices left.
With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.