Fat Loss starts in the kitchen, because fat loss is a result of caloric deficit: you need to burn more calories than you eat. Any physical exercise, running included, helps you increasing the amount of calories burnt, but also makes you hungrier.
To reliably lose fat, you need to a) track the calories that you consume via food and drink, b) track the calories you burn via basal metabolic rate and physical exertion, c) make sure that (b) consistently is a larger number than (a). You probably don't know your basal metabolic rate, though. Just take a generic value (2000 kcal/day seems to be appropriate for your body composition), keep track how your weight changes over time and adjust accordingly. This article provides a good guideline on how to do that - and how much fat loss per week is appropriate.
Running is an easy way to increase your caloric expenditure, to stay healthy in general and has a low entry level. This Book is a good introduction to the topic. It helps you laying out a training routine, explains basic technique, helps you choosing the right running shoes for you etc...
(Aerobic) running and weight training are two fundamentally different biochemical processes. The former doesn't itself 'destroy' muscles, but doing one particularly intense session in one discipline will hurt your performance in the other if done in short succession, i.e. you shouldn't do a 1RM Deadlift on the same day or the day after you just did a high-intensity interval run, and vice versa. If you're interested in how endurance and strength sports go together, I can recommend the book The Hybrid Athlete.
Finally, I think you believe you need way more protein than you actually do. While research suggests an amount of 1.3g-1.8g/day/kg of body weight for optimal results, you should consider this an upper boundary; exceeding it doesn't further increase your performance or muscle gains (Here's a discussion of the latest protein intake research). On the other hand, even if you are below this number, you will still reap the benefit of workouts. A balanced vegetarian diet should easily provide enough protein to overcompensate your training without the need for supplements. If not, ask your parents to get a pound of Skyr everyday, and eat it - done. If you feel sore after 4 months of weight training, that suggests poor form, poor programming or malnutrition. Consider getting a personal trainer and make sure your average caloric deficit isn't too high.
