You can use the »caption« package. See code below for an example derived from the package manual.
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[font=small,labelfont=bf,tableposition=top]{caption}
\DeclareCaptionLabelFormat{andtable}{#1~#2 \& \tablename~\thetable}
\begin{document}
\begin{figure}[!ht]
\centering
\rule{6.4cm}{3.6cm}
\qquad
\begin{tabular}[b]{cc}\hline
Table head & Table head \\ \hline
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\ \hline
\end{tabular}
\captionlistentry[table]{A table beside a figure}
\captionsetup{labelformat=andtable}
\caption{A table beside a figure}
\end{figure}
\end{document}
You will find more details in the manual. This is not exactly what you want, but it would float.

Supplement:
Another solution that would give the desired output. But this won't float.
\documentclass[11pt,a4paper,english]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{babel}
\usepackage[font=small,labelfont=bf]{caption}
\begin{document}
\begin{minipage}{\textwidth}
\begin{minipage}[b]{0.49\textwidth}
\centering
\rule{6.4cm}{3.6cm}
\captionof{figure}{A table beside a figure}
\end{minipage}
\hfill
\begin{minipage}[b]{0.49\textwidth}
\centering
\begin{tabular}{cc}\hline
Table head & Table head \\ \hline
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\
Some values & Some values \\ \hline
\end{tabular}
\captionof{table}{A table beside a figure}
\end{minipage}
\end{minipage}
\end{document}
