Superoptimization is a powerful code optimization technique that generates optimized instruction sequences by exploring the space of instruction-level transformations. However, existing superoptimizers assume that pointers and integers are interchangeable, an assumption that no longer holds in memory-security-enhanced architectures like CHERI, where pointers are represented as metadata-rich capabilities with enforced bounds, permissions, and provenance. This semantic change breaks many traditional optimizations and forces CHERI compilers to adopt conservative strategies that sacrifice performance for safety. We present CapOpt, the first superoptimization framework that explicitly incorporates capability semantics into both its search space and correctness model. CapOpt introduces Provenance-Guided Stratified Synthesis (PGSS), a synthesis strategy that structures the search space around capability-aware abstractions and uses provenance-based reasoning to eliminate unsafe transformations. We also define a capability-aware equivalence model that extends conventional functional correctness to include metadata integrity. We evaluated CapOpt on an ARM-based CHERI hardware platform and the CHERI-RISC-V simulator. Experimental results show that CapOpt improves performance by up to 4.1% over the existing CHERI-LLVM toolchain, while strengthening security by tightening pointer bounds and permissions.