There are substantial challenges. One is that insurance companies don't actually provide care, of course. Any company wishing to do business with people in a particular state would have to actually obtain a network in that state -- partner with an existing network, or negotiate deals and sign contracts with hospitals, urgent care centers, pharmacies, labs, and doctors. They'd presumably have to be licensed to do business in that state, and adhere to that state's own regulations and requirements for doing so. (Because the US is a federal system, the federal government itself is unlikely to be able to strip away all of each state's specific laws and regulations.) This process would have to be repeated for every state in which they plan to do business. Insurance companies would probably set up state-specific legal entities or subsidiaries to provide financial and legal compartmentalization. So selling insurance "across state lines", as a practical matter, may not differ much from the current system. State-specific legal work and shoe-leather network-building would still be required. There's nothing stopping a national company from setting up a state-specific entity and selling insurance this way right now.
Another issue is that if local regulations were somehow stripped, as some in congress wish, insurance companies, as profit-seeking entities, would all gravitate to the most favorable and least regulated business environment. After the Supreme Court ruling in Marquette v First of Omaha, credit card providers migrated to Delaware, South Dakota, or Arizona because those states have the weakest usury laws and allow them to charge rates of 29% or more to borrowers in any other state. A similarly deregulated and "efficient" market for health insurance would have all the companies set up entities in whichever state would allow them to offer plans that provide the least care reimbursement (known internally as "loss control") and charge the highest premium. This could lead to a situation where a few very large companies offer only high-deductible plans without guaranteed issue, excluding procedures that carry risk of being expensive or are politicized, with lifetime or annual caps, thin networks, and retroactive drops. Lip service would be paid in the form of seemingly cheap policies that actually provide little real coverage, but allow insurance companies and politicians to claim "all Americans now have access to affordable health insurance". As bad as the credit card system may be, lending is at least a business that can be conducted at a distance. Health care is the most local of concerns.
What's needed is not a guarantee of "access to efficient health insurance markets". What's needed is actual health care. In a moral society, everybody should have access to that actual care itself without risk of ruin. The US system forces people to make terrible decisions. People remainining in hated jobs, empowering employers and distorting the employer/employee market. Not taking medicine, or half-dosing, because, even with insurance, the costs are too high. Not visiting the doctor after an injured ankle because of fear of the costs, then suffering forever after due to a poorly healed fracture. Especially pernicious: seeing a doctor but not reporting problems because of fear they'd be labeled as pre-existing conditions for which future coverage would be denied. And employers themselves have higher costs because of the historical accident of employer-based insurance, reducing their competitiveness with foreign companies who have no such obligation.
It's a huge political problem, but this focus on insurance, and access to insurance, begs the question.