Grab yourself a copy of VPM-B if you'd like and play with it.
You can set altitude in that deco program, and then run a few NDL profiles on it.
You'll find that if you do this and add 10' or so to your bottom depth (to accomodate the higher surface pressure) you have fairly radical changes in allowed profiles (in the "downward" direction!) before mandatory stops become part of the equation.
As an alternative to sitting at sea level, you could make the dives as if your "surface" was at altitude, and shorten the times and make the stops, if any, required for diving with a surface altitude as set that way. Some computers can be manually set for this (the Suuntos can), or you could use a table program like VPM to generate custom tables for this situation.
IANAD (I am not a doctor!) but the physics of this would appear to line up correctly, as your "final ascent to the 'surface'" at altitude would be MUCH slower than any such program would likely require, and the "depth" from which you would make your ascent would be only 10' fsw or so - extending the 10' stop indefinitely is perfectly fine with these meters and programs.
If I lived at 4000' altitude and wanted to dive at sea level on a regular basis, that's how I'd approach the problem rather than sit around for 12 hours.
Treat the dive as if it took place at 4000' and adjust your profile and deco schedule accordingly.