How to handle wide columns with \backslashbox?

The simplest and most straightforward way of doing this is to specify the literal size of the slashed box. In your case, it's about 40mm. So try this:

\backslashbox[40mm]{foo}{bar}

Generalising this approach would not be much more complicated. Compute the size of the backslashbox by taking the size of the column's widest string then add on two times the width of the table's column separators.

Since this is an issue concerning the slashbox package itself, the only solution might be a hack of the package source. Consider to restructure the table and tweak it with the booktabs package. See code below for some ideas.

\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[font=small,labelfont=bf,tableposition=top]{caption}
\usepackage{booktabs,multirow}

\begin{document}
  \begin{table}[!ht]
    \caption{Table caption}\label{tab:default}
    \centering
    \begin{tabular}{*{4}{|c}|}\hline
      \multirow{2}{*}{foo} & \multicolumn{3}{|c|}{bar} \\ \cline{2-4}
       & test & header & header \\ \hline
      relatively wide column& b & $3$ & $4$ \\
      ds & c & $1$ & $4$ \\ \hline
    \end{tabular}
  \end{table}

  \begin{table}[!ht]
    \caption{Table caption}\label{tab:booktabs}
    \centering
    \begin{tabular}{*{4}{c}}\toprule
      \multirow{2}{*}[-0.5ex]{foo} & \multicolumn{3}{c}{bar} \\ \cmidrule{2-4}
       & test & header & header \\ \midrule
      relatively wide column& b & $3$ & $4$ \\
      ds & c & $1$ & $4$ \\ \bottomrule
    \end{tabular}
  \end{table}
\end{document}

It is also worth to think about dropping vertical lines to improve legibility of the tables as shown above.