In today’s contexts, protecting sensitive information while maintaining usability necessitates privacy-preserving data mining. The Differential Privacy (DP)-based K-means algorithm can achieve this balance by tuning the privacy budget allocation. However, optimizing the privacy budget allocation is a complex task, as it involves striking a balance between privacy protection, data mining performance, and computational efficiency. Motivated by the fact that Evolutionary Algorithms (EAs) can efficiently produce near-optimal solutions, this paper proposes MOMA-DPK, a multi-objective memetic algorithm designed to optimize the allocation of privacy budgets in DP-based K-means clustering. The method balances two competing objectives: maximizing privacy protection by minimizing the total privacy budget spent and preserving clustering utility by minimizing error through the Normalized Intra-Cluster Variance (NICV) metric. By integrating Multi-Objective Optimization (MOO) with an imbalanced local search strategy, MOMA-DPK efficiently explores the privacy-utility trade-off and produces a Pareto front of optimal solutions. Experiments on real-world datasets (heart disease and diabetes) demonstrate that MOMA-DPK consistently outperforms baseline methods—including Naive-DPK, GA-DPK, and NSGA-II-DPK—achieving superior privacy-utility trade-offs and higher hypervolume scores. The source code used in this study is publicly available at https://github.com/Wayne-on-the-road/MOMA-DPK .