Newts can go without feeding for weeks, unless they are already thin and sick. I think the most important thing for you now is to get them into water. You have to make sure the conditions are optimal - tank set up and water quality are very important if you want your newts to be aquatic like they should be. Read this
caresheet and relevant
articles here (housing, water quality etc.- you really need to understand these thigs to be able to look after your newts well).
Your newts need cool water, a small land area and will appreciate lots of live plants. They don't like moving water so a small sponge filter or no filter at all are best options. A secure (preferably breathable) lid is a must.
You will find that feeding them is a lot easier once they are in water. While on land, you need to offer something that moves, earthworms being ideal. In water, they are more likely to accept pellets or defrosted food, even though you should still feed some worms as well.
A lot of people experience similar problems with newly purchased firebellies -
this what searching the Help section of the forum with the keyword "firebelly" throws out. You should spend some time reading through these threads as many deal with the same issues you are having.