Definately stick with the lat pulldowns, they will complement the other things you are doing very well. They aren't as good as pullups, but pullups are a pretty difficult move when you are just starting. It seems like you are hitting most of the major muscle groups. I would suggest adding some kind of ab exercise to round things out a big. A strong core is the foundation of a strong body, you know!
With all those sets to failure, you should be feeling a pretty substantial burn and/or sore muscles the next day. If you feel these things, then I would say yes, you are doing enough. The fact that you don't think you are doing enough makes me think you aren't feeling the burn/soreness the next day. If you are NOT, then your exercises aren't intense enough. As long as you are going to a gym and using machines, I would suggest using enough weight so that you have a difficult time accomplishing 10 reps for your first set, and then failing at less reps on each subsequent set. Really blast those muscles. It will make your workout a lot more intense, and there should be no way you leave the gym wondering whether you did enough or not
BTW, I would say that working up to a 5k isn't really risky chronic cardio territory. Its just lying a bit on the outer boundry of the primal workout range. I ran my first 5k last year or so ago just to prove to myself I could do it, and I still run the distance every week, but I do it for speed now. I'll leave the longer distances to pros.