There's a couple of things I want to add to this discussion/Q&A. First I think it's an interesting exercise to rewrite user10310's reduction from SAT to this problem in a more formal manner. The second bit is an alternative NP-completeness proof that might be a useful starting point for looking for approximation results.
For convenience, let's give this problem a name (the most important step in any complexity result!). Unfortunately, I can't think of a good proper name, so for now I'm going to call it OUR PROBLEM, or OP for short, because that's a nice pun.
Lemma 1 OP $\in$ NP.
Proof. Given a set $S$ we can check that each vertex $v$ in the graph has at most $f(v)$ neighbours in $S$ in polynomial time.
Lemma 2 3-SAT $\leq_{P}$ OP.
Proof. Given an instance $I$ of 3-SAT with variable set $X=\{x_{1},\ldots,x_{n}\}$ and clause set $C=\{c_{1},\ldots,c_{m}\}$, we construct an instance $I'$ of OP as follows:
We create a graph $G=(V,E)$ where
- For each variable $x_{i}\in X$ we have two vertices $x_{i}^{+}$ and $x_{i}^{-}$ in $V$. Denote this subset of $V$ as $V_{X}$.
- For each clause $c_{j}\in C$ we have a vertex $c_{j}\in V$. Denote the set of clause vertices as $V_{C}$.
- In addition there is a set of vertices $V_{Z}$ with $|V_{Z}| = 2n+m+1$.
- For each pair of vertices $x_{i}^{+}$ and $x_{i}^{-}$, we have $x_{i}^{+}x_{i}^{-} \in E$.
- For each clause $c_{j} \in C$, if the literal $x_{i}$ is in the clause we have $c_{j}x_{i}^{+} \in E$, if the literal $\neg x_{i}$ is in the clause we have $c_{j}x_{i}^{-}\in E$.
- For every pair of vertices $z \in V_{Z}$ and $c_{j} \in V_{C}$ we have $zc_{j}\in E$.
We then set the function $f:V\rightarrow\mathbb{N}$ as follows:
$$
f(v) := \left\{\begin{array}{ll}1&\text {if }v\in V_{X}.\\2n+m+3&\text{if }v\in V_{C}\\1&\text{if }v\in V_{Z}\end{array}\right.
$$
Finally we choose $k$ to be $3n+m+1$.
Now we establish certain properties of a solution set $S$ for $I'$.
Proposition At most $n$ vertices of $V_{X}$ are in $S$.
For each pair $x_{i}^{+}$, $x_{i}^{-}$ we can only have one vertex in $S$, otherwise both vertices violate their $f$ value constraint.
Proposition Any solution $S$ contains all the vertices of $V_{Z}$ and none of the vertices of $V_{C}$.
Clearly as $k$ is so large, we need at least some vertices of $V_{Z}$ in $S$, but then if any vertices of $V_{C}$ are in $S$, there is some vertex in $V_{Z}\cap S$ that has at least two vertices in its closed neighbourhood in $S$, which exceeds its $f$ value of $1$. Thus we can have no vertices of $V_{C}$ in $S$. Then $S$ can contain only vertices of $V_{Z}\cup V_{X}$. If we do not include all vertices of $V_{Z}$ in $S$, we have $|S| \leq 3n+m$, thus $S$ is not of size at least $k$, and is therefore not a solution.
So we can see the solution set $S$ is quite constrained, and must take all of $V_{Z}$ and half of $V_{X}$ (which will correspond to a truth assignment).
Proposition If $I$ is a Yes-instance of 3-SAT then $I'$ is a Yes-instance of OP.
If $I$ is a Yes-instance, we have a truth assignment $A:X\rightarrow\{T,F\}$ that satisfies the formula. We construct a set $S \subseteq V$ by taking the vertices of $V_{Z}$ and for each variable $x_{i} \in X$, if $A(x) = T$, we add $x_{i}^{-}$ to $S$, otherwise we add $x_{i}^{+}$. This is clearly a suitable set $S$.
Proposition If $I'$ is a Yes-instance of OP then $I$ is a Yes-instance of 3-SAT.
The set $S$ that constitutes a solution for $I'$ contains $n$ vertices of $V_{X}$, and more particularly, one vertex out of each variable pair. Moreover, as $f(c_{j}) = 3n+m+2$ for all $c_{j}\in V_{C}$, we know that $c_{j}$ is adjacent to at least one vertex in $V_{X}$ that is not in $S$. This vertex then gives us the satisfying assignment for the corresponding variable.
Theorem 3 OP is NP-complete.
Proof. By combining lemmas 1 & 2.
Now I want prove the same thing, but via an alternate route.
Note that the dual problem is the following: Given a graph $G$, a function $g:V(G)\rightarrow\mathbb{N}$ and an integer $k'$, is there a set $S\subseteq V(G)$ with $|S|\leq k'$ such that for all $v \in V$ we have $|N[v]\cap S|\geq g(v)$. To see that this is the dual, starting with OP, we just take $k' = n-k$ and $g(v) = d(v)-f(v)$, where $d(v)$ is the degree of $v$. We then immediately get NP-completeness for OP and dual-OP by observing that DOMINATING SET is a special case of dual-OP; we just take $g(v)$ to be $1$ for all vertices.
Then we know that dual-OP has no $O(\log n)$ approximation unless P=NP (if I recall the result correctly). Unfortunately this doesn't say anything immediately about OP, but is a possible start.