It's not so much a matter of ease or difficulty; rhyming just isn't really a thing in Japanese. I mean, there's a term for it, which I've heard people use when discussing haiku (to refer to internal rhyme or even consonance), but for the most part it's not a thing and people aren't aware of it.

Several times over the years I've had the "hey, were you aware that virtually every English song rhymes from start to finish?" conversation with a number of native JP speakers, and in every case so far they were very surprised. And even when the person is quite fluent in English, although they get the concept intellectually they always have a lot of trouble discerning the rhymes unaided.

This is correct. In Japanese it's so easy to rhyme things that rhymes just aren't interesting or unusual.

I suspect the issue is with the overall rhythm of the sentence - Japanese has its own conventions for intonation, formal rhyming in Romance languages requires an internal structure that may not be agreeable with that.

It might well be that it's easy to the point it's unremarkable.