Ich bin beeindruckt. Das ist ja mal eine vollständige Problembeschreibung.
1. \fbox funktioniert bei mir. siehe Code.
2. Der Abstand kommt im Wesentlichen von \center statt \centering (du beginnst mit \center die center-Umgebung und die fügt zusätzlichen Abstand ein). Ich würde auch die wrapfig floaten lassen. Es kann etwas Bastelei erfordern, die Bilder richtig zu platzieren, aber es ist vieles möglich.
3. Man kann immer einen Zähler manuel zurücksetzen.
Code:
\documentclass[a4paper,10pt]{article}
\usepackage[demo]{graphicx}
\usepackage{floatflt}
\usepackage{wrapfig}
\usepackage{lipsum}
\usepackage{subfig}
\begin{document}
1. Problem
\begin{figure}[!htb]
\centering
\hfill %
\fbox{\subfloat[\label{pic:halle}]{\includegraphics[width=0.45\textwidth]{test.pdf}}
\hfill % alternativ auch \hspace{1cm} für genaue Angaben
\subfloat[\label{abb:ugpoz}]{\includegraphics[width=0.45\textwidth]{test.pdf}}}
\hfill %
\caption{\textbf{1. (ein Rahmen um beide Bilder)}}
\label{pap:th}
\end{figure}
\clearpage 2. Problem: \lipsum[4-8]
\begin{wrapfigure}{L} {5cm}
\centering
\includegraphics[width=0.3\textwidth]{foto.JPG}\\
\caption{titel}\label{fig:aufsch}%
\vspace*{-10pt}%Optional
\end{wrapfigure}
\lipsum[9-15] \clearpage 3. Problem
\begin{center}
\begin{minipage}{\linewidth}
%\centering
\captionof{table}{erster Teil der Tabelle}%
\includegraphics[trim = 18mm 20mm 0mm 28mm, clip]{anhang/potentialeanhang/03Cpot.pdf}
\end{minipage}
\end{center}
\begin{center}
\begin{minipage}{\linewidth}
%\centering
\addtocounter{table}{-1}%
\captionof{table}{zweiter Teil der Tabelle (Forts.)}%
\includegraphics[trim = 18mm 20mm 0mm 28mm, clip]{anhang/potentialeanhang/04Cpot.pdf}
\end{minipage}
\end{center}
\end{document}