Make search result display 1 Company or 2 Companies

$found_posts holds the amount of posts found by a certain query. You can use this logic to display your links

Example:

if ( $allsearch->found_posts <= 1 ) {
    //Dispaly company
} else {
    // Disply companies
}

Just a note on grammar, it should be 0 companies 1 company and x amount of companies after that

EDIT

From the edit I have done to your question, I have the following: To be honest, your code is a bit of a mess, but nothing that cannot be fixed though :-). Lets take a quick run down

• showposts is depreciated in favor of posts_per_page

• wp_specialchars has been depreciated since v2.8.0. You should be using esc_html. But to be honest, I don’t know if it is appropriate here.

• You should not localize HTML tags, just literal text should be localized. Exclude HTML tags from strings to be localized and make use of placeholders

• wp_reset_query() should be used with query_posts which you should never ever use. You should be using wp_reset_postdata() with WP_Query. In this case it is not necessary as you are not setting up postdata or changing the global $post variable

• I’m not very sure if you really need to localize the value of $key

As already stated in the other answer, you can make use of _n() to localize strings with single and plural meaning. As I have already stated, the correct grammar and use is

• 0 companies 1 company and x amount of companies

Your issue is in this line

_e('<span class="resultsFound">( We found '); echo $count . ' '; _e('companies )</span>'); 

We can rewrite it to something like this

$text="<span class="resultsFound">";
$text .= sprintf( _n( 'We found %d company', 'We found %d companies', $count ), $count );
$text .= '</span>'; 
echo $text;

If you really need to display 0 company, you can use

$text="<span class="resultsFound">";
if ( $allsearch->found_posts <= 1 ) {
    $text .= sprintf(__( 'We found %d company' ), $count );
} else {
    $text .= sprintf(__( 'We found %d companies' ), $count );
}       
$text .= '</span>'; 
echo $text;

or

$text="<span class="resultsFound">";
if ( $allsearch->post_count <= 1 ) {
    $text .= sprintf(__( 'We found %d company' ), $count );
} else {
    $text .= sprintf(__( 'We found %d companies' ), $count );
}       
$text .= '</span>'; 
echo $text;