Okay, I did look up other questions and actually I found that I need to use Bevel modifier for this, but due to a way of how my mesh is made, it creates the shape which I don't want, what can I do to remove those "damaged look" parts from my mesh? As you can see below, adding Bevel modifier smooths it out how I wanted it to be smoothed out, but it also smooths out in between the vertices and adds (random?) dents, giving this weird look.
My mesh and problem that occurs:
Any ideas? All vertices (I checked thrice just to make sure and really couldn't find any single one out of place) seem to be in their places (on x plane, all vertices have same x, on y plane they also have same y and so forth...)