What is the problem with illustrator and photoshop?

Hedgewars' graphics are (more or less) based on vector graphics in SVG files. Look out for SVG files. Any program that can edit SVG files should do. I use Inkscape.

However, note that there is no "perfect" SVG editor. SVG is a pretty complicated file format that has so many features that there is no program on the planet that supports all of that. SVG is text-based, so if you're a SVG pro, you can edit SVGs in a text editor. I actually did that myself with some (non-Hedgewars) graphics a few years ago. SVG is quite powerful and cool.

Hedgewars itself actually only supports PNG files, not SVG. We just use the SVG files as "source" to export to PNG. Unfortunately, we don't have vector graphics for everything so far. Attempts to vectorize some images have been mage in the past, but this effort is far from complete. We value SVG images a lot because they much better to edit.
New images should always be vector images so the problem doesn't become worse in future.

Long story short, check if there is a SVG version of the PNG image available, if yes, edit the SVG instead of the PNG.

For SVG, I use Inkscape (but any vector image editor can do, at least in theory).
For PNG, I use The GIMP. But any raster image editor that supports PNG images can do. MS Paint doesn't support PNG (I guess).

As for the "how", I can't really answer unless you are more specific. Basically the same rules apply as for any other SVG/PNG, there is nothing "magic" going on, really.

The melon and grenade should be fairly obvious. Just redraw them to your liking, but try to keep the melon/grenade size the same because otherwise collisions would look so wrong.

you can use free sites like canva or there are lots of videos how to download photoshop

you can use free sites like canva or there are lots of videos how to download photoshop, I have used these programs often when I was living in the property in Czech Republic and working as a SMM manager, they helped me a lot