This has constructible solutions for $n=5,6,8$ or whenever the regular $n$-gon is constructible.
Suppose the vertices of the original $n$-gon are $$(x_1,y_1),\ldots,(x_n,y_n)$$
We are looking to rotate, dilate, and translate the original polygon so that its vertices land on the sides of a canonical regular polygon.
We parameterize the rotation and dilation by $a,b$ and the translation by $v,w$. We let $\phi=\pi/n$. Then the constraints are that for each $i$,
$$\left(\begin{matrix}\phantom{-}\cos 2i\phi &\sin 2i\phi\\
-\sin 2i\phi &\cos 2i\phi\end{matrix}\right)
\left(
\left(\begin{matrix}a &b\\
-b &a\end{matrix}\right)
\left(\begin{matrix}x_i \\
y_i\end{matrix}\right)
+
\left(\begin{matrix}v \\
w\end{matrix}\right)
\right)
$$
is on the side of the canonical regular polygon from $(\cos \phi, -\sin \phi)$ to $(\cos \phi, \sin \phi)$.
The first four constraints give the equations
\begin{align}
(c_2 x_1+s_2 y_1) a + (c_2 y_1-s_2 x_1)b + c_2 v + s_2 w = \cos \phi\\
(c_4 x_2+s_4 y_2) a + (c_4 y_2-s_4 x_2)b + c_4 v + s_4 w = \cos \phi\\
(c_6 x_3+s_6 y_3) a + (c_6 y_3-s_6 x_3)b + c_6 v + s_6 w = \cos \phi\\
(c_8 x_4+s_8 y_4) a + (c_8 y_4-s_8 x_4)b + c_8 v + s_8 w = \cos \phi
\end{align}
where $c_k$ and $s_k$ stand for $\cos k \phi$ and $\sin k \phi$.
So the solutions to these equations for $a,b,v,w$ are constructible from the $x$'s and $y$'s if the $c$'s and $s$'s are constructible. Our procedure for constructing the regular polygon is thus to solve those equations, and:
If these solutions make the other constraints fail, we can not construct a circumscribing regular polygon.
If these solutions make the other constraints hold, then we apply the inverse of the above translation and rotation to the canonical regular polygon. This gives the desired circumscribing regular polygon, and we would get an inscribing regular polygon similarly.
