Star[f_, g_] =
 Sum[(I*h/2)^n*
   Sum[(-1)^k*Binomial[n, k]*D[f[x, p], {p, k}, {x, n - k}]*
     D[g[x, p], {x, k}, {p, n - k}], {k, 0, n}], {n, 0, Infinity}]

Clear[operatorExp];
operatorExp[dop_, n_: 100][f_] := First@FixedPoint[
   {#[[1]] + dop[#[[2]]], dop[#[[2]]]/#[[3]], #[[3]] + 1} &, {f, f, 2},
   n, SameTest -> (PossibleZeroQ[#[[1]] - #2[[1]]] &)]

Clear[poissonOp];
poissonOp[x1_, p1_, x_, p_] :=
  Function[f, I/2 (D[f, x1, p] - D[f, p1, x])];

Clear[star];
star[f_?(PolynomialQ[#, {x, p}] &), g_?(PolynomialQ[#, {x, p}] &)] :=
 Module[{x1, p1},
  operatorExp[
     poissonOp[x1, p1, x, p]][(f /. {x :> x1, p :> p1}) g] /. {x1 :>
     x, p1 :> p}
  ]

star[x, p]

(* ==> I/2 + p x *)

star[x, p] - star[p, x]

(* ==> I *)

star[x, p^2]

(* ==> I p + p^2 x *)

star[x^6 p^2, p^7 x^4]

(*
==> (945 p x^2)/4 - 2205/2 I p^2 x^3 - (2205 p^3 x^4)/4 -
 2205/2 I p^4 x^5 - 840 p^5 x^6 + 42 I p^6 x^7 - (153 p^7 x^8)/2 +
 17 I p^8 x^9 + p^9 x^10
*)

star[f_, g_] := FourierTransform[
   InverseFourierTransform[f, {x, p}, {kf, lf}]
    InverseFourierTransform[g, {x, p}, {kg, lg}]
    Exp[I/2 (-kf lg + kg lf)],
   {kf, lf, kg, lg},
   {x1, p1, x, p}
   ] /. {x1 -> x, p1 -> p}

star[Exp[-x^2 - p^2], Exp[-x^2/2 - p^2/2]]

(* ==> 2/3 E^(1/3 (-3 p^2 + (p - I x)^2 - 3 x^2 + (I p + x)^2)) *)

star[f_, g_] := If[
    Head[#] === FourierTransform,
    # /. {kg, lg, kf, lf} -> {kf, lf, kg, lg}, #] &[
  FourierTransform[
    InverseFourierTransform[
      f, {x, p}, {kf, lf}] InverseFourierTransform[
      g, {x, p}, {kg, lg}] Exp[I/2 (-kf lg + kg lf)], {kg, lg, kf,
     lf}, {x1, p1, x, p}]] /. {x1 -> x, p1 -> p}