If your notion of distance is "vertical distance", similar to how residuals are computed during ordinary linear regression, this problem can be solved with linear programming.
Let $y=ax+b$ be the equation of the desired line; here $a,b$ are unknowns. Suppose we are given a list of points $(x_i,y_i)$. The vertical distance from $(x_i,v_i)$ to the line $y=ax+b$ is
Suppose we want this distance to be at most $d$, where $d$ is given. In other words, we want
$$|ax_i+b-y_i| \le d.$$
This is equivalent to
$$y_i-d \le ax_i+b \le y_i+d,$$
which gives two linear inequalities. (Recall that $x_i,y_i,d$ are known, and $a,b$ are unknown.) Given $k$ points, you get $2k$ linear inequalities. Now you can use linear programming to find $a,b$ that satisfy all of these linear inequalities.
You can even find the minimal value of $d$ such that such a line exists. Simply treat $d$ as an additional unknown, and minimize $d$ subject to the $2k$ linear inequalities above.