I just posted pictures of a Rubik's Cube-style puzzle I made from paper with help from Stella. Unfortunately it's a bit too temperamental to really use as a puzzle, but it does work if you do the twising very carefully and help parts to go where they should.
You might be interested that Martyn Cundy (co-author of Mathematical Models) showed me a "Rubik's" rhombicosidodecahedron that was made from card many years ago.
When it was first made it had worked well, but by the time I saw it it had started to come apart.