How can I get rid of the LaTeX warning: Float too large for page?

The warnings tell you that the float (figure and caption) are too long for staying in a page. You will get rid of many of those warnings if you avoid the center environment:

\begin{figure}
  \centering
  \includegraphics[width=\textwidth]{../fig.pdf}
  \caption[Short caption]{Fairly long text...}
\end{figure}

(it should be avoided anyway, see Should I use center or centering for figures and tables?).

For pretty high figures you might also want to shorten their width, say 0.95\textwidth or less. LaTeX won't apply such a transformation for you: the warning simply tells that a float needs attention, but how to solve the problem depends on factors that only a human can evaluate properly.

If the overfullness is not actually a problem: it worked for me to add \vspace{-Xpt} before the \end{figure}.

In my case the complaint was about an utterly inconsequential 0.04999pt and so I did not want to split the figure or do anything else to the input, just get the useless-in-this-case warning to go away.