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.
I use regularity in the proof of $2 \implies 3$ of from your equivalence (from the problem sheet), but not in the other steps. See my note on this here, if you want to check my proof. It's 3 to 4 there as I add another equivalence with "every open cover has a $\sigma$-locally finite open refinement" in that lemma; so we have it all in one go, so the formulation I chose was the equivalence (for regular spaces) of
- $X$ paracompact (every open cover has a locally finite open refinement).
- Every open cover has a $\sigma$-locally finite open refinement.
- Every open cover has a locally finite refinement (i.e. a cover but not necessarily open).
- Every open cover has a locally finite closed refinement.
- $1 \implies 2$ is trivial and needs nothing, just like $1 \implies 3$.
- $2 \implies 3$ needs no regularity in the proof I gave.
- For $3 \implies 4$, I do use the regularity.
- $4 \implies 1$ also doesn't use it.
Your first result you state is the equivalence of 1 and 2 and I see no path here from 2 to 1 that avoids 3 to 4 somehow... So regularity seems needed.
An example: if $X$ is a Lindelöf Hausdorff, non-regular space, then $X$ obeys the property that every open cover has a $\sigma$-locally finite open refinement (a countable subcover will do that easily) but such an $X$ is not paracompact as a paracompact Hausdorff space is both regular and normal, as is well-known.
Such spaces have been found in abundance (see $\pi$-base e.g., the Arens square and the irational slope topology are the most "famous")
The $F_\sigma$ subset result will hold because Willard (as Engelking) defines a paracompact space to be Hausdorff, and such a space is thus normal and regular, and so the $F_\sigma$ subspace is regular too and the lemma applies to it.
Best Answer
The Sorgenfrey line is a classical example (besides the compact examples mentioned in the thread from the comments), also because its square (the Sorgenfrey plane) is not even normal, let alone paracompact, which shows that products of even 2 relatively nice paracompact spaces can fail to be paracompact.
As a positive result, the product of a paracompact and a compact Hausdorff space is paracompact.