Krename, "a powerful batch renamer for KDE", has a lot of features. Here's a sampling...
- renaming of single files
- renaming of complete directories
- recursive directory scanning with Wildcards (e.g. *.mp3)
- renaming of directory names
- renaming of huge numbers of files (more than 10.000)
- renaming of filename and extension
- sort files in directories
- search and replace using regular expressions
- change file name and/or extension to:
- lower case (e.g. krename.png)
- caps (e.g. KRENAME.PNG)
- first character in word to caps (e.g. Krename.png)
- numbering of files (start,steps,skips definable)
- create subdirectories while renaming
I'm not sure if you can append folder names to names of contained files in one step but given the extensive functionality I'm sure you can automate that work in some way.
"Remove, insert or replace text in the filename" is certainly available.
And as you can see in this screen capture sequential numbering and number padding are present:
Note: I've only experimented a bit with this app (when I was playing around with KDE in a Cygwin/X setup) but I remember it being pretty solid.
Update: A couple other options mentioned over on Software Recommendations SE. Except for the one I mention here they're not KDE specific but it may be worth reading.