I'm new to the CNC world 
I'm having trouble configuring the optimal speed for my machine.
The maximum speed attained depends mainly on how fast your processor can issue step pulses. You have not identified that processor.
How far does the axis move with one motor revolution?
~8 mm.
Could you let me know if I'm at least on the right track 
Are my assumptions so far correct?
Are you trying to control the motor from a standing start, or are you starting off slow and accelerating up to the final speed? Likewise when you approach the point to stop are you slowing down before you stop, or just stopping immediately.
Speeding up and sowing down will allow the speed to be reached to be faster than just starting and stopping.
Yes, I control the motor from standing start. I don't notice any slowing down when starting or when approach the point to stop. How can I do this, and is it really relevant to my questions?
Seems you want a feedrate of 40mm per second, that would be 5 revs per second or 300 RPM or 1000 steps per second with a 200 step per rev motor or 4000 SPS at 4 microsteps. 32 microsteps would require 32000 SPS. I doubt the UNO could do that. Star with 4 microsteps and work your way up until you get missteps or stalls then back down to the next lower setting.
Well it lets you run at a faster speed, which is what your question was all about wasn't it?
I can't tell you this because you have given me no clue as to what hardware you have and what software it is running. It is likely that you will have to modify the software if it is not done by default.
Reducing the micro stepping setting will give you more movement per step and so the motor will run faster, but maybe not as smooth.
You are not endangering anything by playing about with your settings. The only thing that could go wrong is that you will miss steps and so lines will not achieve their full length.
However, don't forget that how fast you can run depends on the load on the motors, which will change depending on what you are cutting.
Ok. Following your logic - now I move 50mm per 6seconds -> ~8mm per second, that would be 1 revolution or 200 steps, but I have 1/32 microstepping so it right now my machine is doing 6400 steps per second. And I don't see any stalls or issues. Does this mean that I should be fine with ~6k steps. I will follow the advice to decrease the microstepping and test. Hopefully I don't break something
I lack the knowledge in the topic and don't see the relevance. Sorry.
I use GRBL 1.1. For the hardware - I sent a link to the board and motors that I bought.
Ok. Thanks.
Can you get 25mm/sec?
Did you set a higher speed for X? Repost your parameter table.
$0 = 10 (Step pulse time, microseconds)
$1 = 25 (Step idle delay, milliseconds)
$2 = 0 (Step pulse invert, mask)
$3 = 4 (Step direction invert, mask)
$4 = 0 (Invert step enable pin, boolean)
$5 = 0 (Invert limit pins, boolean)
$6 = 0 (Invert probe pin, boolean)
$10 = 1 (Status report options, mask)
$11 = 0.010 (Junction deviation, millimeters)
$12 = 0.002 (Arc tolerance, millimeters)
$13 = 0 (Report in inches, boolean)
$20 = 0 (Soft limits enable, boolean)
$21 = 0 (Hard limits enable, boolean)
$22 = 0 (Homing cycle enable, boolean)
$23 = 0 (Homing direction invert, mask)
$24 = 25.000 (Homing locate feed rate, mm/min)
$25 = 500.000 (Homing search seek rate, mm/min)
$26 = 250 (Homing switch debounce delay, milliseconds)
$27 = 1.000 (Homing switch pull-off distance, millimeters)
$30 = 1000 (Maximum spindle speed, RPM)
$31 = 0 (Minimum spindle speed, RPM)
$32 = 0 (Laser-mode enable, boolean)
$100 = 800.000 (X-axis travel resolution, step/mm)
$101 = 100.000 (Y-axis travel resolution, step/mm)
$102 = 800.000 (Z-axis travel resolution, step/mm)
$110 = 500.000 (X-axis maximum rate, mm/min)
$111 = 500.000 (Y-axis maximum rate, mm/min)
$112 = 500.000 (Z-axis maximum rate, mm/min)
$120 = 10.000 (X-axis acceleration, mm/sec^2)
$121 = 10.000 (Y-axis acceleration, mm/sec^2)
$122 = 10.000 (Z-axis acceleration, mm/sec^2)
$130 = 200.000 (X-axis maximum travel, millimeters)
$131 = 200.000 (Y-axis maximum travel, millimeters)
$132 = 200.000 (Z-axis maximum travel, millimeters)
I'm really confused.
Talk about confused! 
Did you set a higher speed for Y? Repost your parameter table.
But, did you change the feed rate for Y axis?
Post the commands you are sending from Arduino to the CNC.
Thanks for you help.
I managed to achieve the desired speed.
I'm marking my replies for deletion as I suppose they are not really "arduino" related, and may confuse someone rather than help.
Sorry, we are unable to communicate, good luck.
Not quite.
Is all you are sending is just three lines?
One of which says:-
G21G91Y-50F800
Do you know what this means?
Feed rate == speed of motor
You think it's doing 6400 sps but its not!
The absolute fastest a Uno can output is ~4000 sps
It can be hard to tell if a stepper motor is actually doing what you tell it to.
If you have a cheap logic analyzer you can test how many sps the Uno is putting out. But that still doesn't tell you if the stepper motor is missing steps.
The only way I know of to test if the stepper is missing steps is to measure how far it moves very slowly then test at faster speeds until it doesn't move exactly as far as it did when going slow. Even then it's possible it was missing steps while going slow. The real key is to see it consistantly move the exact same distance repeatedly many times.
In my now 3yr old project it turned out that after many weeks of use the stepper I thought was good was still missing steps. It would display very small inconsistent variations in distance. That I didn't notice right away. When I finally did get it right my stepper speed is only 1800 sps max but it moves exactly the right distance every single time.