Apologies about the lengthy answer, because it is a simple question but the complexity of the answer is based on the lack of actual details, so I am trying to cover all aspects of it.
I'm part of a cross functional dev team,
Depending on the number/ratio of designers to developers, and the number of products/services that you are working on, the complexity of the user story can vary because of the methods and processes that you have developed (or will develop) to support these activities. For example, if you have a style guide or design system then generally you will see an upfront effort for creating these 'enablers', but then as the project complexity or tasks scale, you will see the benefits of adopting more efficient practices.
You can read more about the design efficiency curve in this A List Apart article.

we are applying Agile and also we are trying to adopt UX.
Normally when your development team is just starting out on the Agile Software Development journey, you'll find that most of the effort is used up estimating and sharing a common understanding about the process and velocity of the team delivering on the points estimated. Many efforts to incorporate UX design practices into Agile have been written about and explored, but in my experience the best way is to treat design tasks like a programming task (but still try to have your own way of doing things) to help communicate what you are doing clearly to the rest of the team. By that I mean break things down into the same block of defining requirements, design a solution, testing that solution and then address any issues or bugs. But you may find different ways that work better with your team, depending on how familiar they are with user-centred design processes.
Now, we have a difficult moment to estimate the UX user stories.
I think this might have something to do with how you are defining and breaking down the epics and the stories. If you have some examples to share that would be good, but generally you want to make sure that epics and stories are structured consistently if you want to be able to estimate them well. If you think about the fact that all user interactions with the system will ultimately be linked back to components that need to be built (and therefore lines of code that will need to be written), the complexity of the design and how it translates to effort in coding (and testing, etc.) should serve as some guide on a baseline to start from, even if it is just an estimation based on t-shirt size (i.e. S, M, L) or the points system that you use (just make it less precise).
What criteria can be involved to estimate the complexity points?
Based on the previous point I made, if you have something that can be used as a reference of the underlying business logic (e.g. BPMN of business processes), technical architecture (e.g. development framework or design system) or user requirements (e.g. user journey map), you can start using some basic principles to create criteria that can be refined to make better estimates later on.
For example, if you start with a user journey map (e.g. of a specific goal or task the user has to perform) and define that as an epic, then each logical step of the process (e.g. based on the user's mental model) could be defined as a particular story, and then all the tasks and subtasks for that step of the process can be the features that need to be designed and implemented. You could do this with the business process as well, and the difference is that you have to map this to a behaviour that makes sense to the user, the same way that if you start with the user's mental model then you have to map this back to how the business system/logic works. The technical architecture will guide you to the way this is mapped out (e.g. using the elements of the chosen development framework or design system).
So now we get to the answer that you are looking for. What can we used as criteria for estimating the complexity? Here are some suggestions:
- steps in the business process that has complexity (i.e. dependencies and bottlenecks) potentially requires a more well-thought out solution
- steps in the user journey that has complexity (i.e. pain points and interactions outside of the system) potentially requires a more elegant design solution
- designs that has complexity (i.e. the development framework or design system doesn't support it out of the box and is not easily extended) requires more effort
- areas of the business process or knowledge about the user that is missing introduces more assumptions and validation, and therefore potential risks plus complexity in estimation because of the unknown factors
Also I'm interested in listening to other similar experiences (UX
Designers that apply Agile).
I think you'll find that most UX designers don't 'apply' Agile to their design process (at least the ones that I have worked with), and personally I prefer to work in a solution/implementation agnostic way (i.e. don't rely on tools and technology, but have a robust approach to solving problems). I've never had any problems approach the design work in the way that I outlined above to get to a logical and reasonable way of estimating the amount of effort required for the tasks that I am assigned. The constant problem that I see in projects is the lack of a clear and consistent way of communicating the process and applying it within the team. Not to mention the constant lack of time and resources to do the work properly adding to the pressure and stress of the situation.