Let $C\subseteq \mathbb{R}^d$ be closed and convex and $x \notin C$.
Question: Is there a direction $v$ such that $$ || (x + \lambda v) - y||_p < || x - y ||_p, \quad \forall y \in C, \; \forall \lambda \in (0, \bar \lambda), $$ where $||\cdot||_p$ is the regular p-norm in $\mathbb{R}^d$ with $1 \leq p < \infty$ and for some $\bar \lambda >0$?
Clearly, for the case $p = 2$, $v$ can be chosen as $(y^*-x)$, where $$y^* = \underset{y\in C}{\arg \min} \; ||x-y||_2.$$ Then there is a hyperplane $H$ with normal $v$ that separates $C$ from $x$. In particular, if we define $b_1 = v/||v||_2$ and let $b_2, \ldots, b_n$ be an orthonormal basis of $H$, we can write $$ x = \lambda_1^x b_1 + \sum_{i=2}^n \lambda_i^x b_i, \; y = \lambda_1^y b_1 + \sum_{i=2}^n \lambda_i^y b_i$$ with $\lambda_1^x < 0$ and $\lambda_1^y > 0$ for every $y \in C$.
Defining $$ x(\lambda) = (\lambda_1^x + \lambda) b_1 + \sum_{i=2}^n \lambda_i^x b_i$$ we get for $0< \lambda < -\lambda_1^x$ and all $y \in C$ $$ ||x(\lambda) - y||_2^2 = (\lambda_1^x + \lambda - \lambda_1^y)^2 + \sum_{i=2}^n (\lambda_i^x - \lambda_i^y)^2 < (\lambda_1^x - \lambda_1^y)^2 + \sum_{i=2}^n (\lambda_i^x - \lambda_i^y)^2 = ||x - y||_2^2.$$
A similar proof might work for general $p$, but since the $p$-norm does not align with the geometry of $\mathbb{R}^d$ so nicely, I am not so sure how.
Let's consider the particular case when $C$ is a half-space. Say $C$ is bounded by a hyperplane with direction the subspace $W$. If there exists such a $v$ like in the statement then $v$ must be such that $t\mapsto \|w +t v\|$ has a (strict) minimum at $t=0$ for every $w\in W$. ( note that this is the "dual" of the "perpendicular vector" to $W$).
Now if $d=2$ such a direction $v$ can be found: take a unit ball in this normed spaces and consider the diameter of direction $W$. The tangent at the end points of this diameter will give the required direction $v$. Note that this is Not in general the vector giving the closest point on $W$-- unless the space is euclidian.
If $d>2$ such a direction does not exist in general. Here where the problem lies. Consider the intersection of a unit ball with a hyperplane of direction $W$ and the intersection of it with the unit ball. The tangent planes at the points of the intersection will not contain the same direction for a general $@$ ( it may happen for some $W$, but not in general). As example, consider the norm $\|\cdot \|_4$ in $\mathbb{R}^3$. Let $C= \{(x_1, x_2, x_3)\ | \ x_1 + x_2 + x_3 = 1\}$.
Keyword: orthogonality in normed linear spaces
$\bf{Added:}$ There is a related problem. This shows that in dimension $\ge 3$ there are counterexamples. Sketch: consider $A_i = (\delta_{ij})_{j=1,3}$ the ends of the coordinate vectors in $\mathbb{R}^3$. Let $p\ge 1$. The solution of the problem :
minimize $\sum_{i=1}^3 \| A- A_i\|_p$
has a unique solution $A=A(p) = f(p) \cdot (1,1,1)$. We have $f(1)= 0$, $f(2) = \frac{1}{3}$ and $f\colon [1, \infty)\to [0, \frac{1}{2})$ is strictly increasing. The point is that the minimizer lies in the convex hull only for the euclidian metric. That shows right away that for $p\ge 1$, $p\ne 2$, the point $A=A(p)$, and the convex set $C= co(A_1, A_2, A_3)$, there does not exist a convenient direction.