How can I create a table of contents with dotted lines all the way to page numbers?

You can update the section and subsection number filler (\cftsecfillnum and \cftsubsecfillnum) and remove the setting inside a box.

\renewcommand{\cftsecfillnum}[1]{%
  {\cftsecleader}\nobreak
  {\cftsecpagefont #1}\cftsecafterpnum\par
}
\renewcommand{\cftsubsecfillnum}[1]{%
  {\cftsubsecleader}\nobreak
  {\cftsubsecpagefont #1}\cftsubsecafterpnum\par
}

The bonus question can be answered from the tocloft manual, page 5. The important term here is ragged right, which is LaTeX/typesetting terminology for 'align left'.

To have the (sectional) titles in the ToC, etc., typeset ragged right with no hyphenation

\renewcommand{\@tocrmarg}{2.55em plus1fil}

where the value 2.55em can be changed for whatever margin space you want.

Actually there is also a user level command \cftsetrmarg to redefine this macro, which is a bit easier to use because it does not require \makeatletter or \renewcommand.

The main question is a bit more involved. The approach shown in the MWE below redefines a macro in which \@pnumwidth is used, such that the required width is computed first, stored in \@pnumwidth and then used to construct the box for the number, which in turn influences the width of the dotted line. The macro is set globally such that it also applies to other places where the macro is used after the calculation.

The solution is a bit quick and dirty, in the sense that 1. it hardcodes values for <10, <100 and <1000, so documents with 1000 pages or more are not handled properly, and 2. the calculations are done in the command for a section title (because this was the top-level entry in the MWE from the OP), which means that it does not work properly for chapters etc., and also if the page number border is between a section and a subsection (e.g., section starts on page 9 with a subsection on page 10) then it will not work. This can be addressed if needed by redefining also \cftsubsecfillnum and similar commands, search the tocloft source for \@pnumwidth to find all the sectioning commands.

MWE:

\documentclass[twoside]{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{multicol} % For having two-columns in TOC and in text
\usepackage{tocloft} % For styling the table of contents
\usepackage{xcolor} % We want to use \fcolorbox
\usepackage{blindtext} % To generate dummy text

%\setcounter{tocdepth}{1} %Control depth of table of contents

% This removes the default TOC heading by redefining the cftmaketoctitle command in the tocloft package
\makeatletter
\renewcommand{\@cftmaketoctitle}{}
% Calculate the desired width of the page number box to influence the length of the dotted line
\renewcommand{\cftsecfillnum}[1]{%
  \ifnum#1<10%
  \gdef\@pnumwidth{6pt}%
  \else%
  \ifnum#1<100%
  \gdef\@pnumwidth{12pt}%
  \else%
  \gdef\@pnumwidth{18pt}%
  \fi\fi%
  {\cftsecleader}\nobreak
  \makebox[\@pnumwidth][\cftpnumalign]{\cftsecpagefont #1}\cftsecafterpnum\par
}
\makeatother
\cftsetrmarg{2.55em plus1fil} % set left alignment for multiline titles

\renewcommand{\cftsecleader}{\cftdotfill{\cftsecdotsep}}
\renewcommand\cftsecdotsep{\cftdot}
\renewcommand\cftsubsecdotsep{\cftdot}

\begin{document}

\setlength\fboxsep{20pt} % Set spacing for the TOC box
\setlength\fboxrule{2pt} % Set border with for the TOC box
\fcolorbox{red}{yellow}{\parbox{\dimexpr \linewidth-2\fboxsep-2\fboxrule}{%
  \centering{\textsc{\Large{Table Of Contents}}}
  \setlength\columnsep{25pt}
  \begin{multicols}{2}
    \tableofcontents
  \end{multicols}
}}

\section{Africa}
\subsection{Angola}
\subsection{Algeria}
\subsection{Benin}
\section{Asia}
\subsection{Afganistan}
\subsection{Armenia}
\subsection{Azerbaijan}
\section{Europe}
\subsection{Albania}
\subsection{Andorra} 
\subsection{Armenia}
\section{North America}
\subsection{Anguilla}
\subsection{Antigua and Barbuda}
\subsection{Aruba}
\section{South America}
\subsection{Argentia}
\subsection{Bolivia}
\subsection{Brazil}
\blindtext[75]
\section{Antarctica}
\subsection{South pole}
\section{Australia}
\subsection{Australia}
\subsection{Tasmania}
\end{document}

Result: