This works per page, but needs at least two LaTeX runs after adding a new heading:
\documentclass{scrbook}
\makeatletter
\AtBeginDocument{%
\if@filesw
\write\@auxout{%
\noexpand\providecommand*\noexpand\minnumwidth[3]{}%
}%
\fi
}
\newcommand*{\minnumwidth}[3]{%
\scr@ifundefinedorrelax{maxnumwidth@page@#2}{%
\expandafter\gdef\csname maxnumwidth@page@#2\endcsname{#3}%
}{%
\expandafter\ifdim \csname maxnumwidth@page@#2\endcsname<#3\relax
\expandafter\gdef\csname maxnumwidth@page@#2\endcsname{#3}%
\fi
}%
\expandafter\gdef\csname pageof@#1\endcsname{#2}%
}
\newcommand*{\makenumberboxof}[1]{%
\scr@ifundefinedorrelax{pageof@#1}{%
#1\autodot\enskip
}{%
\scr@ifundefinedorrelax{maxnumwidth@page@\@nameuse{pageof@#1}}{%
#1\autodot\enskip
}{%
\makebox[\@nameuse{maxnumwidth@page@\@nameuse{pageof@#1}}][l]%
{#1\autodot\enskip}%
}%
}%
}
\newcommand*{\changenumformat}[1]{%
\expandafter\renewcommand\expandafter*\csname #1format\endcsname{%
\begingroup
\settowidth{\@tempdima}{\csname the#1\endcsname\autodot\enskip}%
\edef\reserved@a{\string\minnumwidth{\csname
the#1\endcsname}{\noexpand\thepage}{\the\@tempdima}}%
\if@filesw
\expandafter\write\expandafter\@auxout\expandafter{\reserved@a}%
\fi
\endgroup
\makenumberboxof{\csname the#1\endcsname}%
}%
}
\makeatother
\changenumformat{chapter}
\changenumformat{section}
\changenumformat{subsection}
\changenumformat{subsubsection}
\makeatother
\usepackage{blindtext}
\begin{document}
\blinddocument\blinddocument\blinddocument\blinddocument\blinddocument
\blinddocument\blinddocument\blinddocument\blinddocument\blinddocument
\blinddocument\blinddocument\blinddocument\blinddocument\blinddocument
\chapter{A chapter}
\section{A section}
\subsection{A subsection}
\appendix
\chapter{An appendix}
\section{An appendix section}
\subsection{An appendix subsection}
\end{document}
After the first LaTeX run the headings of the last page are:

but after the third run they are:

Note that it does work only as long as the numbers of chapters, sections and subsections are expandable.
Not numbered headings are still left aligned. So, if I understand your addendum to the question correct, nothing has to be done for those. But if I don't and if this per page solution should also be used for not numbered headings, you have to add additional code, e.g., for the \subsubsection
:
\usepackage{xpatch}
\newcounter{notnumberedsection}
\renewcommand*{\thenotnumberedsection}{\arabic{notnumberedsection}*}
\makeatletter
\xpretocmd{\subsubsection}{%
\let\scr@subsubsection@sectionindent\z@
\ifnumbered{subsubsection}{%
\typeout{subsubsection numbered!}%
}{%
\stepcounter{notnumberedsection}%
\if@filesw
\edef\reserved@a{\string\minnumwidth{\thenotnumberedsection}{\noexpand\thepage}{\string\z@}}%
\show\reserved@a
\expandafter\write\expandafter\@auxout\expandafter{\reserved@a}%
\fi
\scr@ifundefinedorrelax{pageof@\thenotnumberedsection}{%
\typeout{Don't know page of \thenotnumberedsection!}%
}{%
\scr@ifundefinedorrelax{maxnumwidth@page@\@nameuse{pageof@\thenotnumberedsection}}{%
\typeout{Don't know max width for page \@nameuse{pageof@\thenotnumberedsection}!}%
}{%
\expandafter\let\expandafter\scr@subsubsection@sectionindent
\csname
maxnumwidth@page@\@nameuse{pageof@\thenotnumberedsection}\endcsname
\show\scr@subsubsection@sectionindent
}%
}%
}%
}{}{}
This would result in a last page:

but looks very strange in most cases, e.g., page 58 of the example:

If would recommend to not use this! If could be better to number the \subsubsection
using
\setcounter{secnumdepth}{\subsubsectionnumdepth}
DIV17
→DIV=17
,BCOR16mm
→BCOR=16mm
,2.1headlines
→headline=2.1
. See the warnings you get for more information.