Seems to me like TeX Gyre Pagella does have bold small caps:
\documentclass{article}
\usepackage{tgpagella}
\begin{document}
hello \textbf{hello} \textsc{hello} \textbf{\textsc{hello}}
\end{document}

I think your problem is that you're using \sc when you should be using \scshape or \textsc{...}. The commands \bf, \it, \sc, etc. are deprecated and should not be used.
Otherwise, if you load mathpazo without the sc option, you'll get them:
\documentclass{article}
\usepackage{mathpazo}
\begin{document}
hello \textbf{hello} \textsc{hello} \textbf{\textsc{hello}}
\end{document}

They're not real small caps, but sometimes you gotta take what you can get.
Alternatively, (XeLaTeX/LuaLaTeX only) you could buy Palatino Nova, or use Palatino Linotype if you happen to be using Windows:
\documentclass{article}
\usepackage{fontspec}
\setmainfont{Palatino Linotype}
\begin{document}
hello \textbf{hello} \textsc{hello} \textbf{\textsc{hello}}
\end{document}
