The idea behind this expression is indeed a fairly general one.
$\newcommand{\bs}[1]{\boldsymbol{#1}}\newcommand{\calS}{\mathcal{S}}$An entanglement witness $\mathcal W$ is defined as an operator such that $\operatorname{Tr}(\mathcal W\rho)\ge0$ for all separable $\rho\in\mathcal S$, while for some entangled $\rho_{ent}$ we have $\operatorname{Tr}(\mathcal W\rho_{ent})<0$.
Geometrically, this definition is very easily understood as saying that $\mathcal W$ defines a hyperplane in the space of states that separates the separable states from the non-separable ones. Because of the convexity of the space of separable states, any non-separable state can be separated by such an operator (see e.g. (Horodecki 2007) or (Gühne 2008)).
Now forget for a second about states and quantum mechanics. Let $\calS$ denote a convex subset of $\mathbb R^n$ for some $n$, let $ v\notin \calS$, and let $ v_0\in\calS$ be the vector in $\calS$ that is the closest to $ v$ (in standard euclidean distance).
This means that the line (or more generally hyperplane) that is orthogonal to $ v- v_0$ and touches $ v_0$ is tangent to $\calS$ at $ v_0$. Such a "line" is an "optimal" linear separation between $\calS$ and $ v$:

We now simply need to define an operator that tells us on which side of such separation we are in. A natural candidate would be an operator which projects a candidate vector $ w$ on the line $ v- v_0$, or, more precisely, an operator $A$ defined via
$$A w\equiv\langle v- v_0, w- v_0\rangle.$$
Clearly, we then have $A v>0$, and $A v_0=0$, while all vectors in $\calS$ (together with the points on the $\calS$ side of the separation) correspond to $Aw<0$.
To obtain the given expression for the witness you now simply change the sign (because we conventionally define witnesses to be positive on the separable).
In conclusion, you have
$A_{opt} w=\langle v- v_0, v_0- w\rangle$, that corresponds to
$$A_{opt}=( v_0^*-v^*)-\langle v_0, v_0-v\rangle I.$$
where $v^*$ denotes the linear functional $v^*(w)\equiv \langle v,w\rangle$ (or, if you prefer, the bra $\langle v\rvert$).
To get to the expression given in the paper you now just add a normalisation factor, which I guess was added to make something simpler later on in the paper.