How can I redefine \autoref?

The command \IfEq{foo}{foobar}{true}{false} has a true/false argument pair at the end -- this was missing in all tests within the definition of \setlocale, such that \section etc. was gobbled up, leading to being omitted here.

\documentclass{article}
\usepackage{fontspec}
\usepackage{xstring}
\usepackage{hyperref}


\AtBeginDocument{% Must come after hyperref (because hyperref modifies \label and \ref system)
  \let\oldlabel\label% Copy original
  \let\oldref\ref% Copy original
  \let\oldautoref\autoref% Copy original
}

\newcommand{\addlabelsuffix}[1]{%
  \renewcommand{\label}[1]{\oldlabel{##1-#1}}% Update % This works
  \renewcommand{\ref}[1]{\oldref{##1-#1}}% Update % This works
  \renewcommand{\autoref}[1]{\oldautoref{##1-#1}}% Update
  %\show\autoref
}

\newcommand{\locale}{en-US}% Set default locale

\AtBeginDocument{%
  \DeclareRobustCommand{\setlocale}[1]{%
    \renewcommand{\locale}{#1}%
    \addlabelsuffix{#1}% keep labels unique
    \IfEq{#1}{en-US}{%
      \renewcommand{\sectionautorefname}{Section}
    }{}%
    \IfEq{#1}{de-AT}{%
      \renewcommand{\sectionautorefname}{Kapitel}
    }{}%
    \IfEq{#1}{nn-NO}{%
      \renewcommand{\sectionautorefname}{Kapittel}
    }{}%
}%
}

\begin{document}

\setlocale{en-US}% set locale
\section{US English}
\label{test}
First sentence \autoref{test}.

\setlocale{de-AT}% set locale
\section{Austrian German}
\label{test}
First sentence \autoref{test}.

\setlocale{nn-NO}% set locale
\section{Norwegian}
\label{test}
First sentence \autoref{test}.

\end{document}

You're forgetting an argument to \IfEq:

\IfEq{<string-a>}{<string-b>}{<true>}{<false>}

and the false branch is missing. Besides, \ref and \autoref are “robusted” commands, so it's better to use \LetLtxMacro for saving copies of them.

\documentclass{article}
%\usepackage{fontspec}
\usepackage{xstring}
\usepackage{letltxmacro}
\usepackage{hyperref}

\AtBeginDocument{% Must come after hyperref (because hyperref modifies \label and \ref system)
  \let\oldlabel\label% Copy original
  \LetLtxMacro\oldref\ref% Copy original
  \LetLtxMacro\oldautoref\autoref% Copy original
}

\newcommand{\addlabelsuffix}[1]{%
  \renewcommand{\label}[1]{\oldlabel{##1-#1}}% Update % This works
  \renewcommand{\ref}[1]{\oldref{##1-#1}}% Update % This works
  \renewcommand{\autoref}[1]{\oldautoref{##1-#1}}% Update
}

\newcommand{\locale}{en-US}% Set default locale

\DeclareRobustCommand{\setlocale}[1]{%
  \renewcommand{\locale}{#1}%
  \addlabelsuffix{#1}% keep labels unique
  \IfEq{#1}{en-US}{%
    \renewcommand{\sectionautorefname}{Section}%
  }{}%
  \IfEq{#1}{de-AT}{%
    \renewcommand{\sectionautorefname}{Kapitel}%
  }{}%
  \IfEq{#1}{nn-NO}{%
    \renewcommand{\sectionautorefname}{Kapittel}%
  }{}%
}

\begin{document}

\setlocale{en-US}% set locale
\section{US English}
\label{test}
First sentence \autoref{test}.

\setlocale{de-AT}% set locale
\section{Austrian German}
\label{test}
First sentence \autoref{test}.

\setlocale{nn-NO}% set locale

\section{Norwegian}
\label{test}
First sentence \autoref{test}.

\end{document}