The following works:

\documentclass{article}
\makeatletter
\def\@setref#1#2#3{%
\ifx#1\relax
\protect\G@refundefinedtrue
\nfss@text{\reset@font\bfseries ??}%
\@latex@warning{Reference `#3' on page \thepage \space
undefined}%
\else
\expandafter\ifx\csname used@#1\endcsname\relax
\expandafter\global\expandafter\def\csname used@#1\endcsname{used}%
{\bfseries\expandafter#2#1\null}% Formatting of first reference
\else
\expandafter#2#1\null%
\fi
\fi%
}
\makeatother
\begin{document}
\begin{figure}
\centering\rule{150pt}{20pt}
\caption{A figure}\label{fig:figure}
\end{figure}
See Figure~\ref{fig:figure}. The same reference to Figure~\ref{fig:figure}.
\end{document}
It modifies the macro \@setref
which is called from \ref
to decide whether a reference exists or not. The formatting is based on a condition to check whether a newly defined macro used@<label>
exists or not.
Formatting of the first reference is set using \bfseries
and can be modified to suit.