Du musst schlicht darauf achten, dass der Fuß groß genug ist. Die Voreinstellung für `\footskip` liegt in Deinem Beispiel bei ca. 25,3 pt (genauer Wert steht in der Warnung). Im folgenden Beispiel wird der einfach mal eben auf 48 pt erhöht, weil laut Warnung min. 42,4 pt erforderlich sind):
\documentclass{memoir}
\usepackage{lipsum}
\usepackage{lastpage}
\nouppercaseheads
% Voreinstellung in der Log-Datei ausgeben:
\typeout{\noexpand\headheight war \the\headheight, \noexpand\footskip war \the\footskip}
\setheadfoot{12pt}{48pt}
\typeout{\noexpand\headheight ist \the\headheight, \noexpand\footskip ist jetzt \the\footskip}
\makepagestyle{mystyle}
\makeevenhead{mystyle}{Navn Navnesen \& Navn Navnesen}{}{\today}
\makeoddhead{mystyle}{\today}{}{Navn Navnesen \& Navn Navnesen}
\makeevenfoot{mystyle}{}{\rule{4cm}{2pt}\\Side \thepage/\pageref{LastPage}}{}
\thepage/\thelastpage}{}
\makeoddfoot{mystyle}{}{\rule{4cm}{2pt}\\Side \thepage/\pageref{LastPage}}{}
\thepage/\thelastpage}{}
\makepsmarks{mystyle}{%
\createmark{chapter}{left}{nonumber}{}{}}
\pagestyle{mystyle}
\begin{document}
\chapter{Test Chapter}
\lipsum[1]
\section{Test Section}
\lipsum[1-20]
\end{document}
Wenn der Fuß noch tiefer angesetzt werden soll, kann der zweite Wert bei `\setheadfoot` natürlich auch noch größer gewählt werden. Wie groß der Wert min. sein sollte, kann man ja aus der Warnung ablesen. In der Regel ist jedoch ein noch größerer Wert sinnvoll.sinnvoll.
Das Paket `lastpage` ist bei `memoir` übrigens nicht notwendig. Grundsätzlich sollte man bei `memoir` nach Möglichkeit dessen Lösungen für Probleme nutzen, statt externe Pakete zu laden. Diverse externe Pakete funktionieren auch gar nicht korrekt mit `memoir` – `lastpage` aber schon.
