Think equally bold colors to complement or contrast, and give the Calandrinia the space it wants; they can easily get 4~5' across and have 100's of those waving stems full of fuchsia blooms for most of the year. In my view, play off that with bold colors or forms. Phormiums such as Guardsman or Jester or Yellow Wave, coarse foliage plants with stiff upright foliage such as Anigozanthus flavidus, Neomarica caerulea, Chasmanthe floribunda v ducktii, Aristea major or Watsonias work well. Other vivid perennials such as Salvia involucrata, Verbena bonariensis, Alstroemeria 'Ligtu hybrids' or A. aurantiaca, Kniphofia uvaria, etc will stand up to the color, or lower growing ground cover types of things such as Plectranthus neochilus, Kalanchoe pumila, Setcreasia pallida, Lampranthus spectabilis, etc.

Or you could go with a backdrop of cooling silver foliage of Cotyledon orbiculata, Astelia chathamica, Centaurea gymnocarpa or Lavandula intermediate. Succulents such as Senecio mandraliscae, Aeoniums such as Swartzkop or others, agaves and aloes also work well. Agaves with blue or silver foliage can work particularly well, Agave attenuata Nova is a particular favorite, but smaller tougher sorts such as Agave parryi combine well also.

If you are looking for larger flowering shrubs/perennials that can bounce some of the same magenta/fuchsia color around, consider using Isopogon formosus, Fuchsia paniculata, Salvia iodantha, Salvia chiapensis, or deep purple blue things such as Salvia 'Indigo Spires' or some of the vivid Ceanothus such as Concha/Julia Phelps/Dark Star.
Other equally bold flowering plants/shrubs that have the "umpff " to compete might include things like Echoing wildprettii or E. gentianioides, Erythrina x bidwillii or Chamaerops humiliating v cerifera or Dasylrion wheelwright.

Pale blue foliage of grasses such as Leymus condensatus 'Canyon Prince' contrast nicely with the Calandrinia as well, or deeper greens of something like Foxtail Asparagus.