An exemplary multi-access edge computing (MEC) orchestration system obtains an operation parameter of a multi-client application that is to execute on a MEC server to be selected from a set of MEC servers located at a first set of locations within a coverage area of a provider network. When executing, the multi-client application serves respective client applications of a set of client devices located at a second set of locations within the coverage area. Based on the operation parameter, the MEC orchestration system identifies a candidate subset of MEC servers from the set of MEC servers and directs the set of client devices to test and report performance capabilities of the MEC servers in the candidate subset. Based on the reported performance capabilities, the MEC orchestration system selects, from the candidate subset of MEC servers, a particular MEC server on which the multi-client application is to execute.