The topological Hochschild cohomology (that I'll denote now THC) makes sense whenever $A$ is at least an $E_1$-algebra. In particular, you can construct THC of an $E_\infty$-algebra. There is a result called Deligne's conjecture but which is now a theorem stating that THC of an $E_1$-algebra is an $E_2$-algebra. In particular, if you take the homology of THC of something, the resulting graded abelian group has a Gerstenhaber algebra structure. If you take homotopy groups, you get a commutative algebra with a degree 1 bracket but I don't think it's going to satisfy the axioms of a Gerstenhaber algebra in general.

Taking the endomorphisms over $A\otimes S^{n-1}$ is a perfectly fine construction called higher THC. It can be defined as soon as $A$ is an $E_{n}$-algebra although the definition is slightly more involved (a good reference is http://www.math.northwestern.edu/~jnkf/writ/cotangentcomplex.pdf). Higher Deligne's conjecture tells you that this higer Hoschild cohomology is an $E_{n+1}$-algebra. In particular taking homology, you get a Gerstenhaber algebra with a bracket of degree $n$.

Note that in the case where $A$ is $E_\infty$, there is a nice construction of higher THC in the following paper of Ginot Tradler and Zeinalian (they restrict to $E_\infty$-algebras in chain complexes but the case of spectra is similar)
http://arxiv.org/abs/1205.7056

Edit: I just noticed that you were asking more specifically what THC of $KU$ is. It turns out that the unit map $KU\to F_{KU\wedge KU}(KU,KU)$ is an equivalence. The same is true if you replace $KU$ by $E_n$ (the height $n$ Lubin-Tate spectrum). This remains true for the higher dimensional versions of THC. The unit map $E_n\to F_{S^d\otimes E_n}(E_n,E_n)$ is an equivalence. The reason for this is essentially the fact that $E_n$ is étale aver the $K(n)$-local sphere. You can look at http://geoffroy.horel.org/HHC%20of%20the%20LT%20ring%20spectrum.pdf for more details.