Caused by the rising of new network types, e.g., Internet of Things (IoT), within the last decade and related challenges like Big Data and data processing delay, new paradigms such as Edge and Fog computing emerged. Although these paradigms can partially address those challenges, their performance can still be affected by various issues, such as faults or network inefficiencies. To establish efficient network infrastructures for these paradigms, Network Management and Orchestration (NMO) techniques are introduced to improve various aspects of networking e.g., Quality of Service (QoS) provisioning, resource management, task allocation, and many others. Therefore, NMO primarily uses various methods like statistical models, heuristic techniques or Artificial Intelligence (AI) to automate networking decision-making. In this study, we investigate NMO issues, related orchestration challenges and the usage of Machine Learning (ML) techniques as a sub-field of AI for NMO purposes. The focus rests on new Edge-based networking and computing paradigms that employ resource-constraint devices to perform different tasks in environments like Extreme Edge, Cloud-of-Things (CoT) or Mist. We provide a comprehensive survey including a state-of-the-art review, research challenges and future directions. The study shows the challenges of NMO in such paradigms and provides information on how ML-based techniques can improve the performance of Edge-based networking paradigms.