Each method should be not longer than five lines of code

This requirement is nonsensical, and it is not tested.

Each method should be not longer than five lines of code

This requirement is nonsensical, and it is not tested.

• too few tests
• randomness is not really checked: see this solution
• using Test.expect

Missing space: "shouldbe" should be "should be". Try saying that five times fast :)

It would be helpful if this kata linked to part 1 and 2.

These description examples should specify the formatting:

• Example: If you search for sciFfi and cult, than starshiptroopers and spaceballs should be returned.
• Example: If the search is ult, then the suggested tag is cult

These should be:

• "Example: If you search for science fiction, cult, then Spaceballs, Starship Troopers should be returned."
• "Example: If the search is ult, then return Suggested tags for ult is cult."

The needed format for the string was not clear.

I had a viable solution that produced another ordering then the tests expected, which is neither specified nor could I guess a propper ordering by myself to reproduce the test results.

It's good how you're using 'it' to describe what the test should do.
It should be using more generic terms in the description eg:

    it "search for non-existant tag displays no result message" do 
      Test.assert_equals(myFilms.search_movies_by_tags('bromance'), "No suggestions for bromance")
    end

More tests,
Random tests.

You've got one method that is being asked to do multiple unrelated things.
Split these up into appropriately named methods that do one thing.

Needs more tests.
Needs random tests.

Needs random test cases.