Underfull hbox error on tabular context

LaTeX is essentially telling you that you want a table with \textwidth size, but only provide content that is 4 characters long. Maybe the following example shows where the problem is:

\begin{tabular*}{0.9\textwidth}{|l|}
  \hline
  Test \\
  \hline
\end{tabular*}

This produces

which is usually not the intended outcome. The easiest way to fix this is to use the tabularx environment from the package of the same name and use the X column type (which adds filling space).

\documentclass{article}
\usepackage{tabularx}
\begin{document}
\begin{tabularx}{0.9\textwidth}{|X|}
  \hline
  Test\\
  \hline
\end{tabularx}
\end{document}

---

The reason that your example does not compile without \\ is that \hline has to be placed at the beginning of a row. Removing both \\ and the following \hline compiles, but shows the same problem.

It is the way how you are using tabular*. It makes no sense to have the starred version with only one column. In such a case one should use the unstarred version with the p-column specifier. With at least two columns for tabular* you didn't get underfull boxes.

\documentclass{article}
\begin{document}

\begin{tabular*}{0.9\textwidth}{l@{\extracolsep{\fill}}r}\hline
  Test & Test\\\hline
\end{tabular*}

\bigskip
\begin{tabular}{p{0.9\textwidth}}\hline
  Test \\\hline
\end{tabular}

\end{document}