I try to answer starting from the case of square matrices. There is some care to take while considering a "hidden" isomorphism of vector spaces. In any case, let $V$ be a finite dim. vector spaces over a field $\mathbb K$ (for simplicity $\mathbb R$ ), with basis $\{e_i\}$ of cardinality $n$.
It is well known that there exists an isomorphism of vector spaces
$$\Phi:\operatorname{Hom}_\mathbb K(V,V)\rightarrow V^{*}\otimes V, $$
with $$\Phi(\phi)=a_{ij}f_i\otimes e_j,$$
where $\phi\in \operatorname{Hom}_\mathbb K(V,V)$ and $\phi(e_i):=a_{ij}e_j$ for all $i,j=1,\dots,n$.
$\{f_i\}$ is the dual basis on $V^{*}$ of the basis $\{e_i\}$ on $V$, i.e. $f_i(e_j)=\delta_{ij}$.
We use the Einstein convention for repeated indices.
We know how to define the trace operator $\operatorname{Tr}$ on the space $\operatorname{Hom}_\mathbb K(V,V)$; the trace is computed on the square matrix representing each linear map in $\operatorname{Hom}_\mathbb K(V,V)$. Let us move to the r.h.s. of the isomorphism $\Phi$.
- trace operator on $V^{*}\otimes V$
Let
$$\operatorname{Tr}_1: V^{*}\otimes V\rightarrow \mathbb K, $$
be given by $\operatorname{Tr}_1(g\otimes v):=g(v)$.
Lemma $\operatorname{Tr}_1$ is linear and satisfies
$$\operatorname{Tr}_1\circ \Phi=\operatorname{Tr}.$$
proof: just use definitions.
- trace operator on $(V^{*}\otimes V)\otimes\dots\otimes (V^{*}\otimes V) $
Using the $n=1$ case we introduce
$$\operatorname{Tr}_n: \underbrace{(V^{*}\otimes V)\otimes\dots\otimes (V^{*}\otimes V)}_{n-\text{times}} \rightarrow \mathbb K, $$
with $\operatorname{Tr}_n(f_1\otimes v_1\otimes\dots\otimes f_n\otimes v_n):=\prod_{i=1}^n f_i(v_i)$.
Lemma $\operatorname{Tr}_n$ is linear and invariant under permutations on $(V^{*}\otimes V)^{\otimes n}$;
it satisfies
$$\operatorname{Tr}_n\left(\Phi(\phi_1)\otimes\dots\otimes\Phi(\phi_n)\right)=\prod_{i=1}^n \operatorname{Tr}(\phi_i), $$
for all $\phi_i\in \operatorname{Hom}_\mathbb K(V,V)$.
proof: we prove the second statement. We introduce the notation
$$\Phi(\phi_k):=
a^k_{i_kj_k}f_{i_k}\otimes e_{i_k}\in V^{*}\otimes V,$$
for all $k=1,\dots,n$.
We arrive at $$\operatorname{Tr}_n\left( (a^1_{i_1j_1}f_{i_1}\otimes e_{i_1})\otimes\dots\otimes
(a^n_{i_nj_n}f_{i_n}\otimes e_{i_n})\right)=a^1_{i_1j_1}\dots a^n_{i_nj_n}f_{i_1}(e_{i_1})\dots
f_{i_n}(e_{i_n})=\text{remember the definition of dual basis}=
a^1_{i_1j_1}\dots a^n_{i_nj_n}\delta_{i_1j_1}\dots\delta_{i_nj_n}=
a^1_{i_1i_1}\dots a^n_{i_ni_n}\\=\prod_{i=1}^n \operatorname{Tr}(\phi_i),$$
as claimed.
Fix a basis $\{e_1, \ldots, e_n\}$ of $V$, and consider the dual basis $\{f_1, \ldots, f_n \}$ of $V^\ast$. Then we have a basis
$$\{e_1\otimes f_1,\ldots, e_i \otimes f_j, \ldots, e_n \otimes f_n\}$$
for $V \otimes V^\ast$, and the matrix
$$A = (a_{ij})$$
is just a way of representing the element
$$\sum_{i=1}^n \sum_{j=1}^n a_{ij} \; e_i \otimes f_j \in V \otimes V^\ast.$$
Of course an element of $V \otimes V^\ast$ gives a linear map $V \to V$ by
$$(w \otimes f)(v) := f(v) w$$
and extending by linearity. Given two such elements, we can compose the corresponding functions:
$$(w' \otimes f')(w \otimes f)(v) = (w' \otimes f')(f(v) w) = f(v) f'(w) w' = f'(w) \; (w' \otimes f)(v)$$
so composition of linear maps is given by
$$(w' \otimes f') \circ (w \otimes f) = f'(w) \; (w' \otimes f)$$
extended by linearity. If you write your elements in the $e_i \otimes f_j$ basis and apply this operation to them, you'll see that the usual definition of matrix multiplication pops right out.
Of course all the calculations with explicit tensors above can be rephrased in terms of the universal property of the tensor product if you like.
This is all assuming you want the matrix to represent an element of $V \otimes V^\ast$ rather than an element of $V \otimes V$ or $V^\ast \otimes V^\ast$. But you can work out what should happen in cases like that the same way.
Best Answer
Consider matrices $A,B,C,D$ of sizes such that the products $AC$ and $AD$ can be formed. We can use block matrix multiplication to show that $(A\otimes B)\,(C\otimes D)=(AC)\otimes(BD)$.
We will use the notation $A\otimes B = (a_{ij} B)_{ij}$ to denote block matrices, where indices are always supposed to range approriately. Then \begin{align*} (A\otimes B)\,(C\otimes D) &= (a_{ij} B)_{ij}\, (c_{ij} D)_{ij} \\ &= \left(\sum_k (a_{ik} B)(c_{kj} D)\right)_{ij} \\ &= \left( \left(\sum_k a_{ik} c_{kj}\right) BD\right)_{ij.} \end{align*} Note that $\sum_k a_{ik} c_{kj}$ is the $i,j$-th entry of $AC$ so the result is indeed equal to $(AC)\otimes (BD)$.
Since traces of Kronecker products are given as $\operatorname{Tr}(A\otimes B)=\operatorname{Tr}(A) \operatorname{Tr}(B)$, this yields $$ \operatorname{Tr}\left((A\otimes B)\,(C\otimes D)\right) = \operatorname{Tr}(AC) \operatorname{Tr}(BD). $$ In your case that gives $$ \operatorname{Tr}\left((A\otimes B)\,(\overline{A}^T\otimes \overline{B}^T)\right) = \operatorname{Tr}(A\overline{A}^T) \operatorname{Tr}(B\overline{B}^T) = \|A\|_F^2\, \|B\|_F^2, $$ where $\|\cdot\|_F$ denotes the Frobenius norm.