4 weeks - Peninsular Malaysia - Help and hints?

With 4 weeks for Peninsular Malaysia, you will have a good amount of time and you have already done plenty of research, so go with the itinerary you feel most comfortable with, you know best what you like and what you dont like.

For the snorkelling: start with the destination you feel most attracted to (I have been to Tioman and the Perhentians and both are very good for snorkelling. / I havent been to Kapas, so cant comment on it). Depending on the weather and on how you like it, maybe continue to another island for more snorkeling.

I also like to travel by train, and the Man in Seat 61 http://www.seat61.com/Malaysia.htm#.V9gIA9oaySM is great for info on train travel. Travelling by bus will usually be faster.

I would probably add 2-3 days in Singapore, it would be a shame to miss it as you will be so close to it anyway. Im not sure if I would spend much (any?) time in Taman Negara, especially as you have already experienced "better" nature experiences on Sumatra. My favourite place on Peninsular Malaysia is Penang (and there, Georgetown), for the great mix of malay/chinese/indian/western culture, the great food (especially in open air markets) and the overall good atmosphere. But all of the above is me, and what I like ;-).

30 days is a lot of time for peninsular Malaysia and those places you are listing are ok, but probably not enough to fill those 30 days, especially considering that your time on the east coast might be limited by the bad weather.

Middle of October is already quite late for the east coast. You might still find good weather, but don't count too much on it.

Kota Bharu and Kuala Terengganu are not that interesting. Half a day or max. one day are more than enough for each of these cities (and actually there is almost nothing of interest in Kuala Terengganu).

If you insist on staying in west Malaysia and not paying a visit to Sarawak and Sabah, do include these places in your itinerary:

The Royal Belum state park: http://www.molon.de/galleries/Malaysia/WestCoast/Belum/
Ulu Muda: http://www.molon.de/galleries/Malaysia/WestCoast/UluMuda/
Langkawi, in case you can't go to the east coast islands because of the weather
The cave temples around Ipoh: http://www.molon.de/galleries/Malaysia/WestCoast/Perak/ (the city of Ipoh is not that terribly interesting)
Perhaps the Endau Rompin NP
And of course Singapore

One more thing, the Perhentian islands are much, much nicer that Kapas or Tioman. Also the Lang Tengah and Redang islands are nicer than Kapas and Tioman:
http://www.molon.de/galleries/Malaysia/EastCoast/

OP, taking the train from KL to Kelantan is a hassle in my opinion. You need to get to Kuala Lipis first. Look at the train schedules & you'll see.

For Malay culture and history, I'd add Kuala Kangsar and Alor Setar.
For Minangkabau culture, Seramban and Sri Menanti.
I'd also add Taiping.
I also agree with adding Singapore.

I'd definitely not add Langkawi which I consider an overpriced tourist trap.

I agree with Laszlo about adding Taiping - it's Peninsular Malaysia's undiscovered gem. You could easily spend more than 3 days in both Penang and Taiping, particularly Penang.

Chinatown is a good neighborhood to stay in KL, and there are lots of budget hotels around where you can find a private room for less than 100 Ringgit. I've never booked anywhere in advance personally, but if you want to insist on it, try the hostel booking websites or www.travelfish.org for recommendations.

Taiping is sometimes recommended, but I found the place rather unimpressive:
http://www.molon.de/galleries/Malaysia/WestCoast/Taiping/

The city has no (architectural) highlights and the historic core looks like the historic core of many cities in Malaysia

Most of Taiping's attractions are away from the city center: the huge lake, the museum, the zoo and Bukit Maxwell. It is also a good base for visiting Kuala Kangsar.

Also the quiet WWII cemetery, and the nearby mangrove forest along the coast. Plus the town itself has some nice colonial buildings and good hawkers markets. Even the prison's kind of interesting. But if you want to stay away alfredm, suit yourself...

Just a few words to thank you all for your comments and recommendations!
Will check it all and answer later.

BTW I'm putting places on this map just to get an idea of locations and distances. Maybe some others can find it useful.
http://umap.openstreetmap.fr/es/map/malasia-en-2016_100069

Regards!
Colegota