OK I can help you with this because it's what I've been working on for the last three years. Testing, testing and then more testing. First of all, are you a brick and mortar business? When you say you've expanded into new cities does this mean that you have a new store or physical address in these new cities? I'm going to assume because you've got GMB for the new cities that you have a physical address. So the things to consider are these:
There are kind of three types of searcher that I look at when solving these types of SEO problems. You've got searchers who are searching 'product+location' these are actually diminishing in number and more people now are just searching 'product' or 'buy product' or 'product near me' and are using voice and maps and expecting google to know where they are and use their location. So you're right, being in the map pack is key. So I have some traffic from the product+location people and they are usually high commercial intent. They want to buy.
Then the people who just type 'product' and who are near my location will have a higher number of searchers but lower searcher intent. Because they may just be looking for information and happen to be in my city. These are also more difficult to optimise for. Over-optimising location keywords is something to watch out for. But do remember to use the location specific anchor text in your internal linking structure. That's helped me lots. I say something natural(ish) like, For Braces visit our main page: _Braces Liverpool. _This seems spammy but google said slightly over-optimising internal links isn't going to hurt you like external ones will.
Then there are the people not in my city who type 'Product' - this is very high volume and very low commercial intent. Because if you are a local business and someone 100 miles away types in 'product' and you show up, they are unlikely to visit your store.
However, I still optimise for all three of these searchers. I have some articles that are for information only and I want them to rank nationally, pick up TONS of traffic and give my site authority and traffic and send nice user signals to google. I'll often also have the featured snippet or national number one position. These articles almost always also rank locally for Product (where searcher is in vacinity) and product+location. So don't just focus on product+location because you don't get enough traffic and google doesn't give you as much authority.
So you should have your location city name in the URL of your new city locations and optimise for local searchers by getting your local citations absolutely perfect. This means Moz Local, maybe spend some money on a Whitespark Citation Audit. This was the best $300 I ever spent and they helped me get from 4% map pack to 11% and that's out of literally thousands of positions. It's a dynamite service and I'd 100% recommend.
Also bear in mind that your new cities are newer and it takes a few months or even years to start really ranking for local searchers. I've taken - in some cases - 18 months of consistent optimisation and testing to get into the local packs where other competitor services have maybe been there for 5 years! You can't just expect to pop up number one in the map pack straight away. You need to build loads of local and hyper local citations and also LINKS from other local businesses and local partners in those new cities. This takes time and tons of effort. You can't expect to dine out on your strong original city. But also don't expect to internally compete with yourself if you're a new address in a new city with a new location in the URL, business name etc. Re-write the articles for that city like you're starting again but model them on your old successful ones. You'll find doing it a second time it's 100% better than the first.
I'll be honest, I don't know whether it's been all my SEO work or just time that's gotten us to the number one spots locally and on the maps and sometimes I actually find it easier to rank nationally than locally. National ranking is easy. You just need the best article, comprehensiveness and and a strong DA / great click through rate in the serp.
Also I've got the city names in the names of my business. So there's BusinessTown and BusinessOtherTown as the names of the companies. This is really important. Google says it no longer matters about having the name of your product or service in the URL and business title but it's less clear about the location and I've found it to be a massive help. Joy Hawkins or rand might disagree here but this is what I've found from testing it out.
Link signals and GMB signals are the key. Plus lots of reviews for your new location on it's GMB profile. Like 150+ is where it seems to start making a big difference. This is still the best article on the subject. From our friends at Moz. Also check out Joy Hawkins who is the oracle of local and I think she's a mod on this very platform although I might be mistaken. She will have a better answer for you than mine and loves helping people. Also I hope EGOL chimes in because they can help too.
But I'm betting your problem is father time. It's frustrating but Google just doesn't trust newer businesses to take up a spot in the three pack unless you're really giving it gangbusters optimisation in ALL of the areas outlined in the article by moz above.
Hope this helps some. Give us some more specifics to go on and let's get right into it. I love this stuff
PS: There was a very interesting case recently of a Zero Day Exploit where a genius hacker found a way to steal DA from another website - Check it out here it gives us an insight into the fact that google does indeed transfer DA across cities, states and even countries - so give it time (but don't do what this guy did! It's black hat and dangerous stuff. Just an interesting story not a suggestion.