The complexity of contemporary computational tasks necessitates the development of efficient optimization techniques to ensure optimal performance, resource utilization, and satisfaction of constraints. In scenarios where parallel computational power is available, careful selection of the software/hardware configurations to test is even more crucial. This work tackles computationally expensive, constrained black-box optimization problems within cloud computing and High-Performance Computing settings. We propose PAK-MAN (PArallel Knowledge with MAchiNe learning), a novel parallel optimization algorithm leveraging Bayesian Optimization (BO) and Machine Learning (ML) models. PAK-MAN combines the iteration efficiency of BO methods and the ability of ML to predict constrained resources with remarkable accuracy. This integration manages the exploration-exploitation trade-off effectively while avoiding unfeasible configurations. We propose synchronous and asynchronous versions, both with their strengths. We evaluate the algorithm in various scenarios, including cloud resource management, edge computing, and HPC. Comparative analysis with an established state-of-the-art method demonstrates superior performance, improving simple regret by up to 21%.