Have you got the provision for that 3000m restriction? I've used TID for regular trekking trips to Nepal over the last few years. The restriction I think you are talking about relates to snow sports only.
And as someone mentioned, Kathmandu is nothing remotely like 4000m up. Altitude isn't even a minor consideration there.
Just make sure there isn't much or any mountaineering involved. I only found out after a previous trip that I wasn't covered for those parts. Most tea house treks don't have any mountaineering built in but have options for summit diversions which require mountaineering.
And also, if you can avoid it, definitely don't book a tour in advance. If it costs more than $20/day, including all permits, food, drink and accommodation, or $40/day including guide too, it is a rip off.