The following result tells us we can't work over $k$-algebras; as suggested in the comments, this doesn't preclude an example where the algebra is over a commutative ring instead.

Result: Let $A$, $B$ be associative $k$-algebras.  Then $Z(A \otimes_k B) = Z(A) \otimes_k Z(B)$.

Proof: Let $z = \sum_{i=1}^n a_i \otimes b_i$ be an element of $Z(A \otimes_k B)$, and assume wlog that the $b_i$ are $k$-linearly independent.  Since $z$ is central, it must commute with all elements of the form $a \otimes 1$, $a \in A$.  Therefore
\begin{equation*}0 = z(a\otimes 1) - (a\otimes 1)z = \sum_{i =1}^n (a_ia - aa_i) \otimes b_i\end{equation*}
and this holds iff $a_i \in Z(A)$ for all $i$, since $a \in A$ was arbitrary and the $b_i$ are linearly independent.  

We can assume that the $a_i$ are linearly independent in $Z(A)$.  Since $z$ must also commute with all elements of the form $1\otimes b$, $b \in B$, we get that $b_i \in Z(B)$ for all $i$ as well.  Thus $Z(A\otimes_kB) \subseteq Z(A) \otimes_k Z(B)$, and the reverse inclusion is clear.

-------

Let's try to use the fact this fails over $R$-algebras to construct an example.  There are probably simpler ones, but here's what I've come up with.

Let $R = k[x]$, the polynomial ring in one variable.  Define two Ore extensions:

\begin{equation*}
A = k[x^{\pm1},u_1][u_2;\alpha], \quad B = k[x,y,t_1][t_2;\beta]
\end{equation*}
where $\alpha: x \mapsto x, u_1 \mapsto qu_1$, $\beta: x\mapsto x, y\mapsto y, t_1 \mapsto qt_1$ and $q \in k^{\times}$ is not a root of unity.  In other words, $A$ and $B$ are both nearly polynomial or Laurent polynomial, but we've enforced the relations $u_2u_1 = qu_1u_2$ and $t_2t_1 = qt_1t_2$.  $Z(A) = k[x^{\pm1}]$, $Z(B) = k[x,y]$ and we're viewing both of them as algebras over $R = k[x]$.

Now define $z = u_1 \otimes y - u_1x^{-1} \otimes xy$, which is not in $Z(A) \otimes_R Z(B)$ since neither $u_1$ nor $u_1x^{-1}$ are in $Z(A)$.  However,

\begin{eqnarray*}
z(a\otimes b) - (a\otimes b)z &=& u_1a \otimes yb - u_1x^{-1}a \otimes xyb - au_1\otimes by + au_1x^{-1}\otimes xyb \\
&=& u_1a \otimes yb - u_1a \otimes yb - au_1 \otimes by + au_1 \otimes yb \\
&=& 0
\end{eqnarray*}
for all $a \in A$, $b \in B$, using the centrality of $x^{-1}$ in $A$ and the fact that the tensor product is over $k[x]$.  Therefore $z \in Z(A \otimes_RB)$.

(I suppose you could just take $B = k[x,y]$ or even $B = k[x]$ if you prefer, we only really need one ring to be noncommutative for this to work.)