I started in Photoshop.
Start by painting daubs of colour on the plain sky background. Just used the same colours that were in his face, arm and clothes.
Duplicated this layer and used the cutout filter on it (settings: 4/4/2). Pumped up the saturation about 56. Used filter angled strokes (50/15/3) although I'm not sure I needed to do this since I eventually re-texturized the whole thing at the end. Adjusted saturation again and increased it.
Made another duplicate of the original layer with the paint daubs. Used the solarize filter. Then Image-Adjust-Invert. Pumped up saturation by 100.
With the first adjusted layer above this one I set the blend mode to Hard Light.
I then selected the background (easiest to do on the original photo where most of the background is blue sky) and painted into the background (on a new layer) with bright colours.
Added a curves adjustment layer on top to darken everything and a saturation adjustment layer to pump up the saturation yet again ( 42).
Finally I copied the whole thing and took it into Procreate Painter and used the textured clone brushes to make it look more "painted".