Are you hoping for more constant push/pull force or would more start of push/pull force be acceptable?
because of the exponential decrease you'll get in force as the rare earth magnet is pushed away, depending on travel, you will likely alter the force produced and/or acceleration for a portion of it's travel range, but because you are not actually altering the strength of the electromagnet, I don't picture too much difference in constant push force. The metal casing on top bottom and 2 sides of the solenoid is hopefully silicon steel or high permeability steel, and if it's doing it's job well, most of the magnetic field available to repel the rare earth magnet won't extend far past the casing. The permanent magnet may also interact with, for example, the metal of the solenoid's casing in an unexpected way, and it will definitely try to pull itself towards the casing, against the action of the solenoid up until the moment the coil is energized.
It might even pull hard enough to prevent the solenoid from actuating, but what I picture happening is the magnetic field of the solenoid pushing the field of the rare earth magnet at least enough to get it out of the casing(the field, not just the magnet), and possibly accelerating the solenoid faster up to that point, and also acting as a soft brake against forces pushing against the already actuated solenoid. If the fields interact too closely/strongly the rare earth magnet WILL noticeably demagnetize over time.
For the half shmeckel a 1/4" rare earth magnet costs at a hobby store, I'd try it. I have rare earth magnets but no solenoids or I'd test it right now myself and I may have a chance this weekend. Please write again if you do test it. I'm curious. Trying will only break your solenoid if you somehow manage to overcurrent it.
If you want you could also use a Finite Element Magnetic Modeler to check and also visualize the interactions.
Other ways to increase the strength of the solenoid:
1.) Increase voltage/current
2.) Improve magnetic circuit (increase permeability of core and or casing)
3.) Re-wind core with smaller wire and more turns
I think that covers it. If you absolutely can't do #1, I think #2 is your best bet for a quick fix/test. Just surround the core with high permeability material, like iron or ferrite and see if it's measurably stronger.