For simplicity, I will introduce the vector $\vec{z} = (v-\lambda_1,v-\lambda_2)$ so that we may write the optimization problem in question as
$$
f(\vec{z})=\min_{\vec{x}} \{\langle \vec{z},\vec{x}\rangle + \lVert\vec{x}\rVert_2 \}
$$
where $\langle\cdot,\cdot\rangle$ denotes the inner product of the vectors.
If it holds that $\lVert \vec{z}\rVert_2>1$, one may choose $\vec{x}=-\alpha\vec{z}$ for any value $\alpha>0$ such that
\begin{align*}
\langle \vec{z},\vec{x}\rangle + \lVert\vec{x}\rVert_2
&= -\alpha\lVert\vec{z}\rVert_2^2 + \alpha \lVert\vec{z}\rVert_2 \\
&= \alpha\lVert\vec{z}\rVert_2 \left(1 - \lVert\vec{z}\rVert_2\right),
\end{align*}
and thus the minimization problem is unbounded from below. On the other hand, if it holds that $\lVert \vec{z}\rVert_2\leq 1$ then
$$
\langle \vec{z},\vec{x}\rangle \geq - \lVert \vec{x}\lVert_2
$$
holds for any $\vec{x}$.
We may therefore conclude that
$$
f(\vec{z}) = \left\{ \begin{array}{ll} 0 & \text{if }\lVert \vec{z}\rVert_2\leq 1\\-\infty & \text{if } \lVert \vec{z}\rVert_2>1.\end{array}\right.
$$
The dual problem can thus be stated as follows:
\begin{alignat*}{2}
&\underset{v,\lambda_1,\lambda_2}{\text{maximize}} &\qquad& \lambda_1 + \lambda_2 -5v \\
&\text{subject to} & & \left\lVert \begin{pmatrix}v-\lambda_1\\v-\lambda_2\end{pmatrix}\right\rVert_2\leq1\\
& & & \lambda_1,\lambda_2\geq0
\end{alignat*}
In general, I don't think it's very easy, but there are a few things you can do. Firstly $\|x\|_2 \leq \epsilon$ is equivalent to $\|x\|_2^2 \leq \epsilon^2$, that is
$$
\sum_{i=1}^{n}x_i^2 \leq \epsilon^2.\tag{1}\label{1}
$$
You can then introduce $n$ auxiliary scalar decision variables, $t_1,\ldots, t_n$ and replace \eqref{1} by
\begin{align}
|x_i| {}\leq{}& t_i,
\\
\sum_{i=1}^{n}t_i {}\leq{}& \epsilon^2.
\end{align}
In case you cannot handle $\sum_{i=1}^{n}t_i {}\leq{} \epsilon^2$ directly, you can associate with it the penalty function $\psi(t) = \max\{\sum_{i=1}^{n}t_i -\epsilon^2, 0\}$ and define the modified cost function
$$
\tilde{f}(x,t; \lambda) = f(x) +\lambda \psi(t).
$$
This is a Lipschitz continuous and you can apply a penalty method on top of your algorithm (or an augmented Lagrangian method - you have to see which one works better). Simply take $\lambda \to \infty$ and stop once $\psi(t)$ becomes sufficiently small.
Let me just clarify that for each $\lambda$ you will have to solve the following problem
\begin{align}
&\operatorname*{Minimize}_{x,t} \tilde{f}(x,t; \lambda)
\\
&\text{subject to } |x_i| \leq t_i, \text{ for all } i =1,\ldots, n
\end{align}
Update 1. Under the stronger assumption that $f$ is continuously differentiable with Lipschitz gradient, it turns out the the original problem is equivalent to the unconstrained minimization problem
$$
\operatorname*{Minimize}_{x} f(x) - \frac{\gamma}{2}\|\nabla f(x)\|^2 + \frac{\gamma}{2}\operatorname{dist}^2_D(x - \gamma \nabla f(x))^2,\tag{2}\label{2}
$$
where $D$ is the set of box constraints (I'm using the same notation as the paper you cited), and $\operatorname{dist}^2_D$ is the squared distance from $D$, which is easy to compute. The cost function in \eqref{2} is known as the forward-backward envelope of the original problem (see for example this paper).
If $f$ is just Lipschitz the above does not apply. Generally speaking, this is too weak an assumption in optimization (with the exception of global optimization where people resort to branch-and-bound-type methods).
Update 2. You can use a homeomorphism between $B_2 := \{x\in\mathbb{R}^n: \|x\|_2 \leq 1\}$ and $B_\infty := \{x\in\mathbb{R}^n: \|x\|_\infty \leq 1\}$, i.e., a function $\phi: B_2\to B_{\infty}$ such as
$$
\phi: B_{\infty} \ni x \mapsto \phi(x) = \frac{\|x\|_\infty}{\|x\|_2}x \in B_2
$$
for $x\neq 0$ and $\phi(0) = 0$
The inverse is
$$
\phi^{-1}: B_2\ni z \mapsto \phi^{-1}(z) = \frac{\|z\|_2}{\|z\|_\infty}z \in B_{\infty}
$$
for $z\neq 0$ and $\phi^{-1}(0) = 0$.
The constraints in your problem can be written as $\frac{x}{\epsilon} \in B_2$. Define $u = \phi^{-1}(x/\epsilon)$. Then $\frac{x}{\epsilon} = \phi(u) \Leftrightarrow x = \epsilon \phi(u)$. The constraints become
\begin{align}
\frac{x}{\epsilon} \in B_2
\Leftrightarrow{}&{}\frac{x}{\epsilon} \in \phi (B_\infty)
\\
\Leftrightarrow{}&{}\phi(u) \in \phi (B_\infty)
\\
\Leftrightarrow{}&{}u \in B_{\infty}
\end{align}
and the optimization problem becomes
\begin{align}
&\operatorname*{Minimize}_u f(\epsilon \phi(u))
\\
&\text{subject to } -1 \leq u \leq 1
\end{align}
Once you find an optimal solution $u^\star$ (if one exists), you can retrieve $x^\star = \epsilon \phi(u^\star)$.
Best Answer
Let the Lagrangian be: $$L(\mathbf{x};\lambda,\mathbf{\mu})=\frac{1}{2}\|\mathbf{x}-\mathbf{a}\|_2^2+\mathbf{\lambda}^T(\mathbf{x}-\mathbf{b})-\mathbf{\mu}^T(\mathbf{x}+\mathbf{b}),$$ where $\lambda,\mu\in \mathbb{R}^n_+$ and $\mathbf{b}=(b,b,\dots,b)$ is an $n$-long vector with all components equal to $b$. What we did is to convert the constraint $\|\mathbf{x}\|_{\infty}\leq b$ to separable linear constraints $-b\leq x_i\leq b$. The gradient of $L$ will be $$\nabla_x L = \mathbf{x}-\mathbf{a} +\lambda -\mu \overset{\nabla_x L=\mathbf{0}}{\longrightarrow}\mathbf{x}^*=\mathbf{a}-\lambda+\mu.$$ Overall we have $$L(\mathbf{x}^*;\lambda,\mathbf{\mu})=q(\lambda,\mu)=\frac{1}{2}\|\mu-\lambda\|^2+\lambda^T(\mathbf{a}+\mu-\lambda-\mathbf{b})-\mu^T(\mathbf{a}+\mu-\lambda+\mathbf{b})=\\ -\frac{1}{2}\|\mu-\lambda\|^2-\mathbf{a}^T(\mu-\lambda)-\mathbf{b}^T(\mu+\lambda)$$ and your dual problem is $$\max_{\lambda,\mu\in\mathbb{R}^n_+}q(\lambda,\mu).$$
Not the most appealing dual problem I have to admit. We moved from a one variable problem to two variables, and for iterative methods - projecting onto the $l_{\infty}$ ball is a easy as projecting onto $\mathbb{R}^n_+$. Duality comes in handy if we were able to get a problem of lower dimension or a "better" constraint set, which is not the case in hand.