Custom post type and category link together

Hopefully this is what you were asking for?

Make sure you update your permalinks (just click update) afterwards.

This will do yourwebsite.com/vege/%vege-category%/%post%

In your example, you didn’t register the taxonomy type, and additionally you need to add the function to put the category slug into the permalink.

function my_custom_post_vege() {
    $labelsvege = array(
         'name'                 => 'Vege',
        'singular_name'         => 'Vege',
        'add_new'               => 'Add Item',
        'all_items'             => 'All Items',
        'add_new_item'          => 'Add Item',
        'edit_item'             => 'Edit Item',
        'new_item'              => 'New Item',
        'view_item'             => 'View Item',
        'search_item'           => 'Search Recepti',
        'not_found'             => 'No Items found',
        'not_found_in_trash'    => 'No items found in trash',
        'parent_item_colon'     => 'Parent Item'
    );
    $argsvege = array(
        'labels'        => $labelsvege,
        'description'   => 'What type of Vege this is',
        'public'        => true,
        'menu_position' => 100,
        'menu_icon'     => 'dashicons-wordpress',
        'supports'      => array( 'title', 'editor', 'thumbnail', 'excerpt', 'comments', 'custom-fields' ),
        'has_archive'   => true,
        'hierarchical'  => true,
        'rewrite'       => array('slug' => 'vege/%vege-category%','with_front' => false),
        'query_var'     => true,
        'show_in_nav_menus'  => TRUE,
        'show_in_menu'  => TRUE,
        'label'         => 'Veges',
        'publicly_queryable'  => TRUE
    );
    register_post_type( 'vege', $argsvege );
}

add_action( 'init', 'my_custom_post_vege' );

function my_taxonomies_vegetype() {
    $labelsTaxvegetype = array(
        'name'              => _x( 'Vege Category', 'taxonomy general name' ),
        'singular_name'     => _x( 'Vege Category', 'taxonomy singular name' ),
        'search_items'      => __( 'Search vege Category' ),
        'all_items'         => __( 'All vege Category' ),
        'parent_item'       => __( 'Parent Item' ),
        'parent_item_colon' => __( 'vege Type:' ),
        'edit_item'         => __( 'Edit vege Type' ),
        'update_item'       => __( 'Update vege Type' ),
        'add_new_item'      => __( 'Add New vege Type' ),
        'new_item_name'     => __( 'New vege Type Name' ),
        'menu_name'         => __( 'vege Type' ),
    );
    $argsTaxvegetype = array(
        'labels' => $labelsTaxvegetype,
        'hierarchical'  => true,
        'public'        => true,
        'query_var'     => 'category',
        'rewrite'       =>  array('slug' => 'vege' ),
        '_builtin'      => false,
    );
    register_taxonomy( 'vege-category', 'vege', $argsTaxvegetype );
}

add_action( 'init', 'my_taxonomies_vegetype', 0 );

add_filter('post_link', 'category_permalink', 1, 3);
add_filter('post_type_link', 'category_permalink', 1, 3);

function category_permalink($permalink, $post_id, $leavename) {
        if (strpos($permalink, '%vege-category%') === FALSE) return $permalink;
        $post = get_post($post_id);
        if (!$post) return $permalink;
        $terms = wp_get_object_terms($post->ID, 'vege-category');
        if (!is_wp_error($terms) && !empty($terms) && is_object($terms[0]))
            $taxonomy_slug = $terms[0]->slug;
        else $taxonomy_slug = 'no-category';

    return str_replace('%vege-category%', $taxonomy_slug, $permalink);
}