Not an easy question to answer for steppers as there are so many variables, what you are doing is really the only way, all trial and error and also you need to figure out the accel.
Way I did it was set accel low and increased the Vel until I found the max by motor stalling. Dropped that by half then did the same with accel. Then just found a happy medium between Vel and Accel. Personally I think Accel is more important than Vel. As an example I could get 2500mm/min with 40mm/s/s but if I dropped the Vel to 2200mm/min I could get the accel up to 120mm/s/s
With the latter real life machining is faster and much less chance of issues with corner rounding in Constant Velocity.
Hood