SQL Server Execution Plan on server level
There is some confusing info given here. For example, this does not make sense:


  I turn on execution plan it goes to more than 40 seconds.


What do you mean by "I turn on execution plan"? If you are talking about the "Include Actual Execution Plan" option in SSMS, then yes, it does take a moment longer for SSMS to prepare and draw the graphical execution plan. And it certainly takes even longer the first time this option is enabled. Did you run the query several times?

Also, you say:


  When I run query in SSMS, it takes 2-3 seconds


but then say:


  I found out that when language is English (default collation) application works "as quick as possible" (6-7 seconds)


wouldn't 2 - 3 seconds be "as quick as possible"? Or is the application adding 3 - 5 seconds for its processing?

Either way:


  when it language is changed, obviously, SQL server doing recompile and everytime response is more than 40 seconds.


No, not "obviously". A recompile would not explain a 30+ second difference per each execution. But, how are they changing the Collation? Is this dynamic SQL and they are using either nothing or COLLATE Latin1_General..., and then using COLLATE other_lang... for the other language(s)? Not sure how else one could change the Collation for a query. Still, one thing that could explain this difference), if in fact the "collation" is being changed in the way that I just described), is if the column is indexed, in which case I would guess that the column's Collation is [SQL_]Latin1_General_... and so the index is also ordered based on English. If a query is submitted that forces a different Collation by using COLLATE French_..., for example, then the query can't use the index as the rows might be in a different order.

If I am correct about what is going on (O.P. has since confirmed that the situation is as I have described here), then the only way to index the column with multiple Collations is to create non-persisted computed columns to force the Collation for each language being offered. So you can have one column be:

ALTER TABLE [dbo].[SomeTable]
  ADD [ColumnNameFrench] AS ([ColumnName] COLLATE French_100_...);


And then:


create a non-clustered index on [ColumnNameFrench]
update the app code / query so that if someone selects "English", then it selects from [ColumnName], but if the user selects "French", then it selects from [ColumnNameFrench] instead. Then it will be able to use the index on the [ColumnNameFrench].


Hopefully you don't offer too many language options, because I think 10 copies of the index might be a lot.

EXAMPLE

The table:

-- DROP TABLE #Test;
CREATE TABLE #Test
(
  [TestID] INT IDENTITY(1, 1) PRIMARY KEY,
  [SomethingEnglish] NVARCHAR(50) COLLATE Latin1_General_100_CI_AS_SC,
  [SomethingFrench] AS ([SomethingEnglish] COLLATE French_100_CI_AS_SC),
  [SomethingHebrew] AS ([SomethingEnglish] COLLATE Hebrew_100_CI_AS_SC)
);

CREATE INDEX [IX_#Test_SomethingEnglish] ON #Test ([SomethingEnglish]);
CREATE INDEX [IX_#Test_SomethingFrench] ON #Test ([SomethingFrench]);
CREATE INDEX [IX_#Test_SomethingHebrew] ON #Test ([SomethingHebrew]);


Simple stored procedure:

GO
CREATE PROC dbo.Search
(
  @Search  NVARCHAR(500),
  @Language INT
)
AS
SET NOCOUNT ON;

DECLARE @SQL NVARCHAR(MAX);

SET @SQL = N'
SELECT tmp.[TestID]
FROM   #Test tmp
WHERE  tmp.[Something' + 
CASE @Language
  WHEN 1 THEN N'Hebrew'
  WHEN 2 THEN N'French'
  ELSE N'English'
END + N'] = @SearchTerm;';

EXEC sp_executesql
  @SQL,
  N'SearchTerm NVARCHAR(500)',
  @SearchTerm = @Search;
GO