The kind of artwork you like, takes years of study and practice in some quite different disciplines. How long it takes of course depends on the individual.
But being able to create graphics like this is not a "binary" skill which you can learn following a certain course or method. It's an ongoing process.
I don't think you ever get the feeling of "getting there". You have to focus on what you can now and work from there step by step - project by project.
Your Photoshop experience is certainly a plus and learning how to manipulate images and apply effects and textures will probably be relatively easy. Layering in Photoshop is a kind of visual programming.
But the main question is: How to get to the point where there is an image to edit in Photoshop?
Inspiration
To be inspired by a graphic style from another game is not a bad starting point, but you'll also need to find inspiration elsewhere. It could be nature, human behavior, geometric shapes, colors, a historical period, a personal experience, ancient myths - whatever. Being aware of where your inspiration comes from can help you to find more if "the well runs dry".
Imagination
In order to create an image, you'll have to be able to visualize it before your inner eye. Maybe not in detail, but you must at least have some kind of "blurry" sense of how it's going to look.
Research
If you aren't the kind of person who has photographic memory, you'll probably need to do a little research on how the objects you want to put in your image actually looks like.
Illustration
This is the most important and hardest part of the process. At some point you need to actually draw or construct the shapes of your drawing. No matter if you are drawing by hand on paper, using a tablet or constructing vector from scratch, your hand needs to follow every single line of your drawing. The process of learning how to draw takes a lot of passion and determination and can be highly individual. Some illustrators have been drawing since childhood and just never stopped. Others might have gone to classical art school and learned how to draw realistic still-life and croquis. Others again might not have practiced much but are just gifted with a charming personal style. It's an art form and a life style.
I have no idea about your image creating skills, so I can only give you general advice.
If you are drawing stickmen, you should probably lower your expectations and start with making a game about stickmen. You can keep developing your skills on the side so your next project can be a more detailed. It might take years to reach the level of your reference.
If you are already capable of drawing a scene like the ones you like with a pencil on paper, you are not so far away. Then you should focus more on learning the basics of digitizing and colorizing drawings in Photoshop.
