get_category_link() for custom post type does not include custom slug rewrite?

Your category URLs are correct, they won’t change by virtue of being associated with a custom post type. I’ll guess that the problem is that default category queries do not include any custom post types, so will display “Nothing found” on term pages where the only associated posts are a CPT. To fix that, you need to alter category queries via pre_get_posts:

function wpa_cpt_in_categories( $query ){
    if ( ! is_admin()
        && $query->is_category()
        && $query->is_main_query() ) {
            $query->set( 'post_type', array( 'post', 'project' ) );
        }
}
add_action( 'pre_get_posts', 'wpa_cpt_in_categories' );