Cloud Service Brokers (CSBs) facilitate complex resource allocation decisions, efficiently mapping dynamic tenant demands onto dynamic provider offers, where several objectives should ideally be considered. This work proposes for the first time a pure multi-objective formulation of a broker-oriented Virtual Machine Placement (VMP) problem for dynamic environments, simultaneously optimizing the following objective functions: (i) Total Infrastructure CPU (TICPU), (ii) Total Infrastructure Memory (TIMEM) and (iii) Total Infrastructure Price (TIP) while considering load balancing across providers. To solve the formulated multi-objective problem, a Multi-Objective Evolutionary Algorithm (MOEA) is proposed. Considering that each time a demand (or offer) change occurs, a set of non-dominated solutions is found by Pareto-based algorithms as the one proposed, different selection strategies were evaluated in order to automatically select a convenient solution. Additionally, the proposed algorithm, including the considered selection strategies, was compared against mono-objective state-of-the-art alternatives in different scenarios with real data from providers in actual markets. Experimental results demonstrate that a pure multi-objective optimization approach considering the preferred solution selection strategy (S3) outperformed other mono-objective evaluated alternatives.