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.)