The documentation & function name could be a bit clearer. How's this?

/** Find the largest segment of consecutive selected curve points, starting from \a start_index.
 * \param r_segment_start_idx returns the start index of the segment.
 * \param r_segment_len returns the number of curve points in the segment. 
 * \return whether such a segment was found or not.*/
static bool find_fcurve_selected_segment(...)

selected can be declared as const bool here. That way its scope is clearer, as well as the fact that it's no longer changed once set.

Based on the function name & documentation, it should just find fcurve segments, and not also do some other task. If that other task cannot be avoided, it must be documented as part of the responsibilities of this function.

Nice to have such explanation in the code, makes it super easy to follow.

I'm not a fan of if (condition) return true; else return false; constructs, as those basically are the same as return condition;. In this case I do like the comments, so I'm not 100% convinced the code simplification makes things clearer. What do you think of this @Christoph Lendenfeld (ChrisLend) ?

/* If the last curve point was in the segment, `r_segment_len` and `r_segment_start_idx`
 * are already updated. */
return in_segment;

I think this changes some of the semantics. In the original code, the selection was maintained, and can_decimate_all_selected = false then makes sense. In the new code, the keyframe is deselected when it cannot be decimated. Not only does this change the user's keyframe selection, it also makes the "can decimate all selected" concept a bit weird -- after all, once this code is done running, everything that is still selected can still be decimated.