Maybe, but if the POD involves Elizabeth dying of plague, you could easily have Katherine die off in the same outbreak as well.
England was still majority-Catholic at this point, and Elizabeth's religious policies had been very controversial (the Act of Supremacy only passed the Lords by a margin of 19-21; given that the people voting against it were voting against the clearly-stated religious beliefs of the queen, that's a very slender margin). If Mary decides to bring England back to the Catholic fold, she'd have a lot of support and a high chance of success. Scotland would be more difficult, as the Reformation there was less of a top-down affair; one possible outcome would be for Mary to use the resources of England to reimpose Catholicism north of the border. Admittedly such a move would probably be against her character, as she seems to have been disinclined to force her religion on people, but depending on who she marries her husband might push for it.
Eh, the notion that England was mostly Protestant this early on is based on outdated historiography, which in turn was largely based on Protestant propaganda which portrayed the Catholic Church as a hated foreign body which was eagerly rejected by the English people as soon as they got the opportunity. Modern historians, as far as I've seen, don't generally think that England became majority-Protestant until several decades into Elizabeth's reign, and that was mostly because Elizabeth herself lived long enough for all the previous clergy to die or retire and get replaced with Protestants.
At the time Wales, Ireland and Northern England would likely be firmly Catholic, and Scottish Highlands and Northeast was dominated by the Earl of Huntly, a crafty politician who supported the Lords of Congregation in 1560 but was nevertheless firmly Catholic(the PoD happened before he refused Mary her entry to the castle). Edinburgh, Aberdeen and Glasgow would likely be mixed, while London and the modern-day Home Counties would be strongly Protestant. In such a scenario, it would be extremely dangerous if Mary was going to hold her coronation in Westminster Abbey with the newly-appointed Catholic Archbishop of Canterbury(likely a Scottish bishop educated in the Scots College of Paris, as most English bishops had sworn the Oath of Supremacy and thus were unfit for a Catholic service), as Protestants would try to block her and the Archbishop from access to the Abbey.
Back in Scotland, John Knox would start ranting again, as the laws passed by the Reformation Parliament in Scotland and Elizabeth I's first Parliament would be replaced by Mary's own version of religious compromise as new Parliaments were summoned. Knox would try to influence the Burgh Commissioners(in Scotland) or the MPs(in England) to vote against the new religious settlement, but as OTL, a compromise would still be reached.
The age difference with Charles IX is too big for that match being seriously considered plus Catherine de’Medici do not wanted her as daughter-in-law (or she would have been engaged to Charles just after Francis’ death and married him as soon was possible) and is unlikely who Mary will take it in consideration after inheriting England.
Charles, Prince of Asturias or Archduke Charles are much more likely husbands for her in this situation
Archduke Charles would be a probable choice, but the Archduke's territory was far away from either Edinburgh or London and neither Styria, Slovene lands, nor Scotland or England could afford having an absentee monarch. An additional danger would be the Archduke's support for active counter-reformation policies, which would endanger Mary's plan for general religious peace.
Marrying either John Hamilton, son of the Earl of Arran, or Lord Darnley would be politically dangerous. Don Carlos was simply not a viable candidate.
If extinguished of any viable marriage plans by either the Scottish or English Parliament, Mary and/or the Scottish/English Parliament could simply declare Charles, second son of the Earl of Lennox, as the heir to the throne of both realms, or legitimize Lord James, Earl of Moray, and make him her heir. In such scenarios, if Mary died as OTL, either Arbella Stuart would succeed the throne at the age of 11, or Elizabeth Stewart, Countess of Moray, would succeed the throne at the age of 22. Mary's OTL lifespan was actually slightly longer than that of an average member of the House of Guise, and longer than most Stewarts, so an 1587 death would still be likely even if Mary died naturally on her bed in the Holyroodhouse or Windsor Castle.
In a TL in which Francois II and Mary had a daughter(which is my favourite scenario), Mary or the Guises might try to make a match between the girl and Henri of Navarre, thus unifying the claims of Valois and the claims of Edward III with the claims of Joan II of Navarre, but the Scottish/English Parliament or the Estates of Bearn would not approve this marriage, as Mary's realms and Henri of Navarre's realms would be too distant from each other and hard to access(as Bearn and Navarre were landlocked, and opponents of Henri of Navarre could block the path from the seaport to Lower Navarre).