private:

    bool rm(KUrl itemToDelete);

const KUrl &

void CleanUpDirectory::setupDirectories()

        // The documentation sais it should be 1 or 2. But actually it only works with 0.

Which docu is wrong? I see 0, 1, and 2 being mentionned both in KIO::stat and in StatJob::setDetails.

OK actually that's for stat(), I don't see any docu for the metadata "details" used by ListJob. Where did you see one?

void CleanUpDirectory::setupDirectories()

        entriesJob->exec();

OUCH, nested event loops are evil, and even more so in kded. Please don't use KJob::exec here. Just let the job run.
It will autodelete itself, so no need for kill either.

void CleanUpDirectory::setupDirectories()

        KFileItem file(entryList.at(i), KUrl(mCurrentURL, entryList.at(i).stringValue(KIO::UDSEntry::UDS_NAME)), true);

Q_FOREACH would make this simpler and faster (no need to call .at(i) twice)

Also, there's a KFileItem constructor that takes a UDSEntry as input. This way it won't have to stat() again every file, to get its attributes and size.

void CleanUpDirectory::setupDirectories()

        sorted.insert(mEntriesToSort.at(i).time(KFileItem::ModificationTime) , mEntriesToSort.at(i));

It would be much faster to sort mEntriesToSort itself, rather than copying into a different container.
Just use qSort(begin, end, predicate) and write a predicate function which sorts two kfileitems the way you want them sorted.

void CleanUpDirectory::setupDirectories()

    // sort the entries by ModificationTime

The comment is wrong, this code is sorting by size [use a different predicate function]

void CleanUpDirectory::setupDirectories()

    // sort the entries by ModificationTime

... :)

void CleanUpDirectory::setupDirectories()

// TODO:

what's the todo? implementing "deleting the oldest"? (better put the TODO inside the method then ;)

void CleanUpDirectory::setupDirectories()

    // FIXME: Can not delete files with %20 in the filename

Probably due to double encoding. Might be fixed by my suggestion of using KFileItem(UDSEntry).

void CleanUpDirectory::setupDirectories()

        delJob->exec();

Don't use exec. Since these are always local files, I would suggest simply QFile::remove(itemToDelete.localPath());