Lv 56-58 is more than enough. Lv 40 is adequate for Vegnagun. Your choice of DS is very good also. I don't know the sequence to jump on the pillars, I tend to jump all over the place and eventually I end up where I want to be.