How to edit default Commerce Order status?
Ryan's solution in Change order status string from "Completed" to "Shipped" works finally, my code was wrong. 

So, for anyone having the same need, create a mini-custom module using the function hook_commerce_order_status_info_alter (dependencies commerce_order) and paste your new label like it is done for Completed status. 

You may find the exact status machine names (e.g. "pending") in commerce_order.module.