What is the limit number of \label in a document?

Look at the end of the .log file, where it says "Here is how much of TeX's memory you used:..."

4,000 labels should be no problem at all with a reasonably modern TeX implementation, unless you use insanely long labels. In fact 40,000 labels in a document would probably work fine. (FWIW, I vaguely remember running out of memory at about 60,000 once, a few years ago).

There is usually some way to increase the memory allocation if you need to. The way to do that depends on what version of TeX you have installed, so you need to read the documentation.

the number of labels is probably not an issue these days but as you do not need forward references there is no need to write all that data to a file to be read back, you can just save the data in commands without writing to the aux file.

% file mchoice.tex
% arara: latex: {draft: yes}
% arara: latex
% arara: dvips
% arara: ps2pdf
% arara: clean: { files:[mchoice.aux, mchoice.log, mchoice.out,mchoice.dvi,mchoice.ps] }
\documentclass{article}
\usepackage{enumitem}
\usepackage{multicol}
\usepackage{pgffor}
\usepackage[colorlinks]{hyperref}
\usepackage{refcount}
\usepackage{tcolorbox}
\tcbuselibrary{many}

% Set key for multicols in enumitem
\SetEnumitemKey{columns}{before=\begin{multicols}{#1},after=\end{multicols}}%

% Custom label for save choice key
\makeatletter
\newcommand{\customlabel}[2]{%
   \expandafter\xdef\csname#1\endcsname{#2}%
   \hypertarget{#1}{}%
}
\makeatother

% Create a environment mchoice, scope enumerate and \keych
\NewDocumentEnvironment{mchoice}{m}{%
\label{#1}
% values for multicols 
\setlength{\multicolsep}{5.0pt plus 2.0pt minus 1.5pt}
% values for enumitem
\setenumerate{parsep=3.5pt,partopsep=3.5pt,topsep=3.5pt,labelsep=5pt, leftmargin=*, itemsep=0pt,widest=80}%
\setenumerate[1]{labelsep=5pt,itemsep=1pt,label=\arabic*.}
\setenumerate[2]{leftmargin=16pt,nosep,itemsep=0pt,label=\Alph*)}
% Command to save key choice
\NewDocumentCommand\keych{o}{%
\IfNoValueTF{##1}%
    {\customlabel{#1:\arabic{enumi}}{\Alph{enumii}}}%
    {\customlabel{#1:\arabic{enumi}}{\string##1}}}% close \keych
}%
{%
\customlabel{max:#1}{\arabic{enumi}}%
}% close mchoice

% Create a command to all key for test
% #1 : pass to tcolorbox
% #2 : name
% #3 : ref
% #4 : columns
\newcounter{last}
\DeclareTotalTColorBox{\keytest}{ O{} m m O{4}}
{ size=small,top=-1mm, left=0mm,width=\columnwidth,%
  adjusted title=center,halign title=center,title filled,fontupper=\small,%
  fonttitle=\small\sffamily,adjusted title={#2},center title,#1}
  {% 
  \begin{enumerate}[columns=#4,leftmargin=15pt,labelsep=3pt,font=\small,nosep,widest=25]%
  \small
  \setlength{\columnsep}{0pt}%
   \edef\tmp{\noexpand\foreach \noexpand\x in {1,...,\csname max:#3\endcsname}}%
   \tmp{%
    \item \hyperlink{#3:\x}{\csname#3:\x\endcsname}%
    }
  \end{enumerate}%
}%

\begin{document}
\section{National Prov}

\begin{mchoice}{paa-1985-a}
\begin{center}
\textbf{PAA 1985 (A)}
\end{center}
\begin{enumerate}
\item First type of questions
    \begin{enumerate}% 
        \item value 
        \item value 
        \item value
        \item correct \keych
        \item value 
    \end{enumerate}
\item Second type of questions
        \begin{enumerate}[leftmargin=3pc,label=\Roman*.]
            \item $2\alpha+2\delta=90^{\circ}$
            \item $\alpha=\delta$ 
            \item $\angle EDF=45^{\circ}$
        \end{enumerate}
\begin{enumerate}[columns=2]% 
        \item I only 
        \item II only \keych
        \item I and II only
        \item I and III only 
        \item I, II, and III
\end{enumerate}
\item Third type of questions
        \begin{enumerate}[leftmargin=3pc,label=(\arabic*)]
            \item $2\alpha+2\delta=90^{\circ}$
            \item $\angle EDF=45^{\circ}$
        \end{enumerate}
    \begin{enumerate}[columns=2]%  
        \item Altenativa A 
        \item Altenativa B \keych
        \item Altenativa C
        \item Altenativa D
        \item Altenativa E 
    \end{enumerate}
\item Fourth type of questions (these need manual tuning for alternatives, 
      usually carrying pictures or tables)
\begin{center}
\noindent
\hspace*{0.75cm}\includegraphics[scale=0.15]{example-image-b}
\end{center}

\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline A)
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline B)
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline C)
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline D) \keych[D]
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline E)
\end{minipage}
\item Fifth type of questions, a problem with numerical response \keych[\$2]

\end{enumerate}
\end{mchoice}


\begin{mchoice}{paa-1985-b}
\begin{center}
\textbf{PAA 1985 (B)}
\end{center}
\begin{enumerate}
\item First type of questions
    \begin{enumerate}% 
        \item value 
        \item correct \keych
        \item value 
        \item value
        \item value 
    \end{enumerate}
\item Second type of questions
        \begin{enumerate}[leftmargin=3pc,label=\Roman*.]
            \item $2\alpha+2\delta=90^{\circ}$
            \item $\alpha=\delta$ 
            \item $\angle EDF=45^{\circ}$
        \end{enumerate}
\begin{enumerate}[columns=2]% 
        \item I only 
        \item II only 
        \item I and II only
        \item I and III only \keych
        \item I, II, and III
\end{enumerate}
\item Third type of questions
        \begin{enumerate}[leftmargin=3pc,label=(\arabic*)]
            \item $2\alpha+2\delta=90^{\circ}$
            \item $\angle EDF=45^{\circ}$
        \end{enumerate}
    \begin{enumerate}[columns=2]%  
        \item Altenativa A 
        \item Altenativa B 
        \item Altenativa C
        \item Altenativa D \keych
        \item Altenativa E 
    \end{enumerate}
\item Fourth type of questions (these need manual tuning for alternatives, 
      usually carrying pictures or tables)
\begin{center}
\noindent
\hspace*{0.75cm}\includegraphics[scale=0.15]{example-image-b}
\end{center}

\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline A)
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline B)
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline C)
\end{minipage}
\begin{minipage}{0.2\textwidth} \centering
\includegraphics[scale=0.15]{example-image-a}\newline D) 
\end{minipage}
\begin{minipage}{0.2\textwidth}
\centering
\includegraphics[scale=0.15]{example-image-a}\newline E) \keych[E]
\end{minipage}
\item Fifth type of questions, a problem with numerical response \keych[\$3]

\end{enumerate}
\end{mchoice}

\section{Answer key}
\begin{multicols}{2}
\setlength{\columnsep}{0pt} 
\keytest{PAA 1985 (form A)}{paa-1985-a}[5]
\keytest{PAA 1985 (form B)}{paa-1985-b}[5]
\end{multicols}
\end{document}