I know that the product of a compact space and a paracompact space is paracompact, and that in general the product of two paracompact spaces are not paracompact.
Question: Is there a weakest condition on a space $Y$ such that $X \times Y$ is paracompact Hausdorff for every paracompact Hausdorff space $X$??
So you are looking for conditions $P$ such that, for all $X$ paracompact Hausdorff and all $Y$ with condition $P$, $X \times Y$ is paracompact Hausdorff.
Clearly such a condition $P$ needs to imply Hausdorff paracompactness itself (but $P$ = "paracompact Hausdorff" does not work, as you stated already, and as the Sorgenfrey line shows).
This paper by Suzuki already mentions a few $P$ that work:
He also proves a more general $P$ than both of these. Morita already showed that for a metric space $Y$ it is in fact necessary and sufficient to be a union of a sigma-locally finite collection of compact subsets in order to have the property that the product with any paracompact space is again paracompact, which is closely related to the Michael line example (which shows that the irrationals times a paracompact space need not be paracompact).
This paper has even more conditions and a nice survey.