The key idea is indeed to use the "tube lemma", as d.t. did in his solution, but there is a small gap in his solution.
(This proof does not assume prior knowledge of tube lemma)
Let $X$ be paracompact and $Y$ be compact. Let $\mathcal{A}$ be an open cover of $X\times Y$.
(Tube lemma part) First fix $x\in X$, and for each $y \in Y$, find $A\in\mathcal{A}$ and basis element $U\times V$ such that $(x,y)\in U\times V\subseteq A$. As $y$ ranges in $Y$, these various $U\times V$ cover $\{x\}\times Y$, which is compact. Thus there exists finitely many $U_1\times V_1 \subseteq A_1,\dots,U_n\times V_n\subseteq A_n$ that cover $\{x\}\times Y$. Let $U_x = U_1\cap \dots \cap U_n$. For later use, let $\mathcal{A}_x=\{A_1,...,A_n\}$.
Now, $\{U_x\}_{x\in X}$ is an open cover of $X$. Using paracompactness, there is an locally finite open refinement $\mathcal{B}$ that covers $X$. For purpose of notation, suppose $B_i,i\in I$ are the elements of $\mathcal{B}$. Using the refinement property, for each $i\in I$, pick $x_i\in X$ such that $B_i\subseteq U_{x_i}$.
Consider the open refinement $\mathcal{C}$ of $\mathcal{A}$ given by
$$\mathcal{C_{x_i}}:=\{A\cap (B_i\times Y)\}_{A\in \mathcal{A}_{x_i}},\quad \mathcal{C}:=\bigcup_{i\in I}\mathcal{C}_{x_i}$$
To prove that this is a cover, consider any $(x,y)\in X\times Y$. First $x$ is in some $B_i$. Since $\mathcal{C}_{x_i}$ covers $B_i \times Y$, $(x,y)$ is covered by $\mathcal{C}$.
To prove that it is locally finite, consider any $(x,y)\in X\times Y$. First there exists an open neighbourhood $U\subseteq X$ of $x$ that intersects only finitely many elements of $\mathcal{B}$, say $B_1,...,B_m$. Then $U\times Y$ is the desired neighbourhood of $(x,y)$ that only intersects finitely many elements of $\mathcal{C}$ as it can only intersect elements from $\mathcal{C}_{x_1},...,\mathcal{C}_{x_m}$, each of which is a finite collection.
Every $a \in A$ is in some $V_\beta$ (as these form a cover of $X$).
But then $a \in V_\beta \cap A \in \mathcal{V}$. These trivial facts prove two things: $\mathcal{V}$ is non-empty if $A$ is (this is a necessary condition for (1) to hold of course), and $\mathcal{V}$ is a an open cover of $A$. (so 1 and 3 hold).
$\mathcal{V}$ refines $\{U_\alpha\}_{\alpha \in I}$: let $V_\beta \cap A$ be an arbitrary non-empty member of $\mathcal{V}$. Then $V_\beta \subseteq U'_\alpha$ for some $\alpha \in I$ (it cannot sit inside $X\setminus A$ because then its intersection with $A$ is empty). So $V_\beta \cap A \subseteq U'_\alpha \cap A=U_\alpha$, and we're done.
$\mathcal{V}$ is locally finite. Let $a \in A$. Then we can find a neighbourhood $N_a$ (in $X$) of $a$ so that $N_a$ intersects at most finitely many members of $\{V_\beta\}_{\beta \in J}$. But then $N_x \cap A$ also intersects at most finitely many sets (as many or fewer than before) of the form $V_\beta \cap A$ ($\beta \in J$) and this is a neighbourhood of $a$ in $A$. So $\mathcal{V}$ is locally finite.
There's no more to it than that. Besides remarking that a subspace of a Hausdorff space is also Hausdorff, but you rightly focused on the cover aspect of the definition.
Notice the similarity to the proof that a closed set of a compact space is again compact.
Best Answer
Unfortunately, the interior of $A$ is not so helpful--for instance, it could easily be empty. But there's something much simpler you can do: each $U_\alpha$ is of the form $V_\alpha\cap A$ for some $V_\alpha$ that is open in $X$. Now consider the open set $V=\bigcup V_\alpha$.
Details on how to finish are hidden below.