Mathematica, 194 224 192 bytes

""<>Cases[HornerForm@MinimalPolynomial[ToExpression@#,x]//.{Times->t,x^a_:>Fold[#2~t~#&,x~Table~a],a_~t~b_~t~c_:>a~t~t[b,c]},a_~b_~_:>{b/.t:>"*"/.Plus:>If[a>0,"+",""],ToString@a," "},{0,∞}]&

Here ∞ is the three byte unicode character representing infinity in Mathematica.

Since input is a string, 13 bytes are lost on ToExpression@ which interprets the string input as an algebraic expression.

HornerForm@MinimalPolynomial[2^(1/2)+3^(1/2), x]

Would return something like

1 + x^2 (-10 + x^2)

The next replacement rule massages this into something that is structurally like

1 + (x * (x * (-10 + (x * (x)))))

This Horner form can be visualized like a tree:

We, by the rules of OP start out with the deepest leaf on the right.

Cases goes through the expression, starting at the deepest level, taking each parent node and its left leaf and assembling this into a table such as

"*" "x"   " "
""  "-10" " "
"*" "x"   " "
"*" "x"   " "
"+" "1"   " "

""<> concatenates everything with the empty string.

SageMath, 108 bytes

def f(s):p=map('{:+} '.format,numerator(minpoly(sage_eval(s)/1)));return'*'+p[-1][1:]+'*x '.join(p[-2::-1])

Try it on SageMathCell.

Explanation:

Evaluate the string symbolically as an algebraic number (sage_eval()). Every algebraic number is a zero of some polynomial a[0] + a[1] x^1 + a[2] x^2 + ⋯ + a[n] x^n with rational coefficients a[0], …, a[n] (minpoly()). Multiply all the coefficients by their common denominator to turn them into integers (numerator()), then write this polynomial in the desired output format,

*a[n] +a[n-1] *x +a[n-2] *x … *x +a[1] *x +a[0]

SageMath, 102 bytes, almost

lambda s:(lambda a,*p:'*%d'%a+'*x'.join(map(' {:+} '.format,p)))(*numerator(minpoly(1/sage_eval(s))))

This works for all inputs except 0, because a polynomial for 1/α is a polynomial for α with the coefficients reversed. :-(