Path-following solvers constraint equations driven by the maximum of a selected mechanical field (e.g., strain variation, elastic predictor of the damage criterion function, damage increment, etc.) are widely used in finite element computations owing to their robustness. However, the presence of the maximum operator renders these constraint equations non-differentiable, thereby precluding the use of standard Newton-type algorithms. As a consequence, monolithic solvers become impracticable, and formulations require ad-hoc iterative procedures to enforce the constraint. This contribution introduces a family of path-following algorithms based on regularized maximum constraints, which restore differentiability and enable fully consistent Newton-based solution strategies also enabling efficient solver parallelization. After providing the theoretical and numerical formulation, providing error bounds and asymptotic behavior of the employed approximation, the application to regularized damage mechanics computations using a eikonal nonlocal damage model is shown, as an example, considering a regularized constraint on the maximum of a scalar measure of the strain tensor. After proposing a Newton-like solver for the the eikonal non-local damage model, several test cases characterized by stable and unstable structural responses induced by material softening are illustrated to analyze the performances of the proposed formulation also compared to a standard solver employing a nested interval algorithm for solving the path-following constraint equation. Possible extensions ad hoc developed for the eikonal damage models are finally discussed, using differential geometry concepts for formulating robust path-following solvers.