How to increase the numwidth for a part in ToC?

With a KOMA-Script class there is no additional package needed. You can use

\RedeclareSectionCommand[
  tocnumwidth=2cm
]{part}

to change the space for the part number in TOC to 2cm.

Code:

\documentclass{scrbook}

\RedeclareSectionCommand[
  tocnumwidth=2cm
]{part}

\setcounter{part}{2011}
\begin{document}
\tableofcontents
\part{First part}
\chapter{A chapter}\section{A section}
\chapter{A chapter}\section{A section}
\part{Second part}
\chapter{A chapter}\section{A section}
\chapter{A chapter}\section{A section}
\part{Last part}
\chapter{A chapter}\section{A section}
\chapter{A chapter}\section{A section}
\end{document}

Using the tocloft package, you can redefine \cftpartnumwidth:

\documentclass{scrbook}
\usepackage{tocloft}

\renewcommand\cftpartnumwidth{2cm}

\begin{document}

\tableofcontents

\setcounter{part}{2011}
\part{Test Part}

\end{document}

Another option, not requiring additional packages is to redefine \l@part as defined in scrbook.cls; here's such a possible redefinition:

\documentclass{scrbook}

\makeatletter
\renewcommand*\l@part[2]{%
  \ifnum \c@tocdepth >-2\relax
    \addpenalty{-\@highpenalty}%
    \addvspace{2.25em \@plus\p@}%
    \setlength{\@tempdima}{2cm}% original value: 2em
    \if@tocleft
      \ifx\toc@l@number\@empty\else
        \setlength\@tempdima{0\toc@l@number}%
      \fi
    \fi
    \begingroup
      \parindent \z@ \rightskip \@pnumwidth
      \parfillskip -\@pnumwidth
      \leavevmode
      \advance\leftskip\@tempdima
      \hskip -\leftskip
      \usekomafont{partentry}{#1\nobreak
        \usekomafont{partentrypagenumber}{\hfil\nobreak
          \hb@xt@\@pnumwidth{\hss#2}}}\par
      \ifnum \scr@compatibility>\@nameuse{scr@[email protected]}\relax
      \endgroup
      \penalty20010
      \else
          \penalty\@highpenalty
      \endgroup
    \fi
  \fi
}
\makeatother

\begin{document}

\tableofcontents

\setcounter{part}{2011}
\part{Test Part}

\end{document}

Since you are using KOMA-Script, you could have a look at the package tocstyle.

\usepackage{tocstyle}
\usetocstyle{KOMAlike}

This requires extra compilation runs to calculate the widths of the TOC.