That's an article I wrote a few years back. Pleased it's still of interest
You're right in that it is not about recording CV, but some of the approaches in that device might be useful for altering CV afterwards. I've not looked at it for a while, but being able to move sets of points, or shape every x curve is pretty fun.
As for the CV record, I agree that selective sampling is perhaps the key. You could easily sample at changes of direction (which would record a saw wave for example) or at points after x change has occured to create approximations.
Curve values can also be set with messages, so there is scope for this to work. The curve approximation stuff is definitely the complex bit that's not inbuilt in Max. @jasonw22 - do you have a good source for that info?
I'm sure the journey will be interesting though - feels the sort of project that could easily end up as something completely different from the intention, but just as useful.
another thought - ej.function is also a great graphical function eidtor - and has a few different options: http://www.e--j.com/index.php/ej-function/
Forgetting the whole translate into function part of this, just recording CV then playing it back (in various ways) is probably going to be useful for a lot of people here. Altering the playback with other CV or functions is also potentially interesting, as is tools for doing things like inverting, smoothing, modulating etc on playback.