See Theorem 13.9 in Rudin's real and complex analysis, 3rd edition.
Your idea is the good one : what you need is the notion of compact exhaustion of $A$, that is a sequence of compact sets $K_n$ such that $A=\cup K_n$,
each $K_n$ lies in the interior of $K_{n+1}$, every compact subset of $A$ lies in some $K_n$, and every component of $\overline{\mathbb{C}} \setminus K_n$ contains a component of $\overline{\mathbb{C}} \setminus A$.
The construction of such $K_n$'s can also be found in Rudin, Thm 13.3.
Proof: Since $K$ is compact, we may impose the following assumptions on $K$:
- $K$ consists of a finite union of closed balls.
- The poles of $K$ are contained in the interior $K^\circ$.
Let $z_1,z_2,\ldots,z_k$ be the poles of $f$ in $K$ with multiplicities $m_1,m_2,\ldots,m_k$. Define $q(z)=(z-z_1)^{m_1}\cdots(z-z_k)^{m_k}$, and define $g(z)=f(z)/q(z)$, which is analytic on some neighborhood of $K$. As in user zhw.'s solution here, we can find a sequence of rational functions $\{t_n\}$ such that $t_n\to g$ uniformly on $K$, and each $t_n$ has all of its poles in $A$, and for each $z_i$, each $t_n$ matches the value of $f$ and its first $m_k$ derivatives at $z_i$. That is,
$$\begin{array}{rcl}
t_n(z_i)&=&g(z_i)\\
{t_n}'(z_i)&=&g'(z_i)\\
&\vdots\\
t_n^{(m_k)}(z_i)&=&g^{(m_k)}(z_i).
\end{array}$$
Define $r_n=t_n/q$. Then each $r_n$ has all of its poles in $A\cup A_f$.
CLAIM: $r_n\to f$ uniformly on $K$.
Fix $\epsilon>0$, and define $M=m_1+m_2+\cdots+m_k$. Choose a $\delta>0$ small enough so that at each pole $z_i$ of $f$ in $K$, the disk $B_{z_i}(3\delta)$ is contained in $K^\circ$, and contains no other poles of $f$ other than $z_i$. Pick some $N>0$ such that for all $n>N$ and $z\in K$, $|t_n(z)-g(z)|<\epsilon\delta^M$.
Therefore if $z\in K$, with $|z-z_i|>\delta$ for all $i$, we have
$$|r_n(z)-f(z)|=\dfrac{|t_n(z)-g(z)|}{|q(z)|}<\dfrac{\epsilon\delta^M}{\delta^M}=\epsilon.$$
Now, for each $i\in\{1,\ldots,k\}$, the assumption on the function $t_n-g$ has a zero at $z_i$ of multiplicity $m_k$. Therefore $r_n-f$ is analytic on is analytic at $z_i$, and therefore on all of $K$. Now, for each $i\in\{1,\ldots,k\}$, $r_n-f$ is analytic on $B_{3\delta}(z_i)$, and has magnitude less than $\epsilon$on $\partial B_{\delta}(z_i)$, so by the maximum modulus theorem, $|r_n-f|<\epsilon$ on $B_{\delta}(z_i)$.
We have $|r_n-f|<\epsilon$ on $K$, so we conclude that $r_n\to f$ uniformly on $K$.
Best Answer
Let $U_n = \{z: n \geq Re(z) \geq \frac{1}{n}, |Im(z)| \leq n\}$, $V_n = \{z: -n \leq Re(z) \leq \frac{-1}{n}, |Im(z)| \leq n\}$. Let $f_n: U_n \cup V_n \cup [-in, in] \to \mathbb{C}$ be defined as $f_n(z) = 1$ for $z \in U_n$, $f_n(z) = 0$ for $z \in [-in, in]$, $f_n(z) = -1$ for $z \in V_n$. $f_n$ is holomorpic, and $K_n = U_n \cup V_n \cup [-in, in]$ is compact subset of a complex plane, and $\bar{\mathbb{C}} - K_n$ has only one component, so if we take $S = \{\infty\}$, there's a rational function $p_n$ that only has poles in $S$, such that $\sup_{z \in K_n} |f_n(z) - p_n(z)| < \frac{1}{n}$. As $p_n$ has only pole at infinity, it's a polynomial. It's easy to see that sequence $p_n$ satisfy the requirements, because each $z \in \mathbb{C}$ is in $K_n$ for all $n$ starting from some $n_0$.