Our challenges with Scrum on system enhancement (multiple Scrum teams, change management in a large company)

we are looking to take some changes on the way we operate

Who is looking to do that? Are senior leadership recognizing and communicating a need for change?

From what you describe, you've got a Scrum Master, an IT team, and perhaps others who are ruling out certain changes and gravitating back to waterfall.

UAT and Deployment
Our scrum master doesn't believe that UAT and the deployment should be part of the Scrum. How are we supposed to track the Definition of Done in such case? A lot of user stories fall out of vision because of that.

I have seen multiple posts where it says that UAT and deployment should be part of it. Anyone have experienced either or both ways?

Without knowing more specifics about your context and what, exactly, "UAT" and "deployment" mean to your organization, I would typically agree with your Scrum Master.

In my experience in regulated industries, there is often a formal acceptance period. When I worked on embedded systems in aerospace, a new version of a system went to an integration lab where it the aerospace integrator tested in in a lab, then on an aircraft on the ground, and then finally on a flying test aircraft, before approving it for use. In SaaS software for the pharmaceutical industry, the customers need an opportunity to perform validation and this validation comes in the form of a required UAT window in a pre-production environment that they have access to and can perform their tests and capture records of their testing to satisfy their internal processes that conform to the regulations.

In cases like this, it doesn't make sense to require the UAT and deployment to production to be part of the Definition of Done. The Scrum Team - or even the developing organization as a whole - may not have any control over when the testing gets done prior to accepting the work. It doesn't make sense for the team to have an external entity gate when they consider work done.

My preference is to have the Definition of Done be work that is within the control of the Scrum Teams. Done should be defined in a way that would allow their work to sail through any of these customer or user acceptance activities. Although customers and users may have feedback for upcoming iterations, it shouldn't be feedback that blocks the acceptance of the work. If there is a defect or issue found that blocks acceptance, the team should treat that as seriously as a failure in a deployed system, which, in my experience in regulated industries, often involves root cause analysis, identifying corrective and preventive actions, and implementing product and process improvements to mitigate such issues in the future.

Dependencies between Product and Scrum Team

We have multiple Scrum teams for different products within the same system and they can have technical dependency between them. The proposed solution is to have a Scrum Change Board before each Sprint Planning in order to review each user story and identify clear dependencies to avoid issues. This would, according to me, lengthened the overall Sprint process.

My suggested approach would be to have better system/data glossary whereby we can map and find any kind of dependency between the different products and processes. (This would take time to implement and maybe we would need an interim approach?) Each implementation of user story must refer to this guide and inform the other team that cooperation is needed. Once the user story is completed, we would update it in case of any change.

This is an issue with refinement.

For within a single product, I would look toward Nexus' Cross-Team Refinement and LeSS's Product Backlog Refinement for some possible solutions. Refinement is where you should be identifying these types of issues. If you can identify Product Backlog Items that have a dependency and what that dependency is, you can take proactive steps in how you order the Product Backlog or what team does the work.

Across products, I would look for ways to eliminate, or at least reduce, dependencies. Without knowing more about your context, it's hard to say what is possible or what makes sense. However, looking to standards and developing to interfaces are common solutions. Involving the teams with dependencies as stakeholders at Sprint Reviews and perhaps even in refinement could also be beneficial.

Change Management

We are having difficulties to offer the proper change management to ensure that we inform the right people without too much information. We have built communication channel for each product but people haven't been very engaged. 
One of the proposed idea is to move to a quarterly type of releases and general communication combining all products. 

Although it feels like it would help, releasing less frequently adds risk. You will have more changes in each release, and each change is an opportunity to introduce an issue. And, when an issue inevitably arises, having more changes will make it harder to diagnose which change(s) caused the issue so you know where to look for a solution.

I would recommend digging deeper into why people aren't engaged. I would look to your Sprint Reviews for potential solutions. If the right people are present and engaged, they should be aware of not only what the team has done in the previous Sprint, but the state of the Product Backlog going into the next Sprint. Ensuring that the Product Backlog for all products is visible and transparent outside the Sprint Review can also help.

Solution design

Our IT team doesn't want to have the refinement cycle where we prepare continously the user story and solution within the Scrum team. They would like to hold solution design session where we bring the solution architect each time to discuss the solution and ensure the right solution. With that, they would like to embed an additional step in the Sprint to block some time to confirm the solution before we go into planning.

I don't understand what problem this is attempting to solve. Gating the team's ability to design and deliver solutions on a single "solution architect" seems very risky. Although it could be useful, especially in a scaled environment where multiple teams are working on a single product or you have a portfolio of multiple products and need someone to monitor for consistency across those products, I would encourage the system architect to be empowering the people on the team. Instead of being a gate, this person (or, ideally, these people) should be setting up standards and guardrails for the team and then coaching the team or working with the teams when the standards or guardrails don't make sense (and perhaps updating them).

It seems to me that we lose a lot of agility from these suggested approaches. We are just moving back toward the waterfall approach.
I would like your opinion on what do you think? How have you been implementing Scrum in your organization?

It does seem like most, but not all, of the proposed solutions are moving away from agility. But some may make sense for your context. Not all contexts need an extreme amount of agility. Understanding the risks of losing some agility in favor of control could help make a more informed decision.